Research Of MAC Scheduling Technology Based On Graph Algorithm In Wireless Sensor Networks

The wireless sensor network can achieve the quantitative collection, fusionprocessing and wireless transmission of the date, so it has been widely used in industry,agriculture, military, and other fields, and the further research of the wireless sensornetwork has been done by people. Because of the combination with technology ofmedia, the wireless sensor network needs more demanding bandwidth, therefore moreand more attention is paid on the problem of bandwidth. The MAC (Medium AccessControl) layer protocol builds on hardware directly, and it is the basis of the otherlayers of wireless sensor network, so MAC layer restrict or even determine theperformance of the whole network largely. Therefore, it is significant to improve theutilization of bandwidth from MAC layer.The characteristics and classification of the MAC protocol of wireless sensornetwork is discussed in this thesis. According to the access of channel, summary andanalysis of the existing MAC protocol is concluded. Also, advantages anddisadvantages of every kind of MAC protocol are discussed in this thesis.Based on the existing MAC protocol, the STDMA-G (Space Time DivisionMultiple Access-Graph) node scheduling algorithm which is based on a noveldistributed graph algorithm is proposed. On the assumption of the primaryinterference model, the model of network topology is converted into graph. Based onthe knowledge of graph, the node whose degree or r is the maximal among itsneighbors has a preference for joining MIS when the balanced state emerges，andfinally the MIS is obtained. Next, every node of the MIS colors its neighborsdistributedly. Finally, according to the result of coloring, every node obtains its timeslot, and therefore the transmission collision is avoided improving the utility rate ofbandwidth. The algorithm is fully distributed and its time complexity is proved to beO (log*n)theoretically. And also with the small information overhead in schedulingprocess, the energy consumption is saved effectively.In addition, the technology is simulated and performed by simulation softwareand hardware platform. The simulation result by VC reveals that the convergence timeis lower obviously as compared with the existing best algorithm; Many networks aremodeled and simulated by OPNET simulation software, and the result reveals thelarger of the network, the better of this scheduling technology; The result of the Gainshardware reveals the scheduling technology can improve the reliability of wireless sensor network effectively.