Energy Efficient Wireless Sensor Network Routing Algorithm

The routing algorithm for wireless sensor networks (WSNs) has muchdifference with algorithm applied in classic networks, and it needs to not only realizethe function of finding routes from the source to the end, but also need to completethe whole process which includes activating sensor nodes, maintaining routing andtransmitting data. The research for WSNs routing algorithm is the important methodto improve the efficiency of networks and promote the application of WSNs, andnow it is one of the most attractive research fields in computer science. In WSNs, allsensor nodes’ energy is provided by battery embedded in nodes, and it is limited, andhow to make the best use of this energy is the key of prolonging the lifetime ofWSNs. So energy efficiency is one of most important standards to judge theperformance of WSNs. There are many existed research for WSNs to improve itsenergy efficiency, but these researches are mostly pay the attention to a special phaseof WSNs routing such as some ones focus on improving the performance in findingand maintaining routes, and some ones emphasis are on polishing up the efficiencyof locating sensor nodes, and some ones pay the attention to reduce the transition ofredundant data. There is few researches consider from overall network layer toimprove WSNs’ energy efficiency.According to these analyses, we research the key problems of WSNs energyefficiency from the view of overall scope of network layer from activating andlocating nodes to steady transmitting information in this paper. And based on theoverall analysis to the features of energy efficiency, a series of researches includingnodes location, building and updating routes and data aggregation are make, andthree related algorithms are proposed. And use these algorithms, the different phasesin WSNs’ network layer are integrated, and the energy efficiency is improved overall.And the main innovations of this paper are introduced as follows:1. Based on the analysis of existing models of WSNs, a general model forWSNs is defined. The most of existing researches for WSNs have the defaultsincluding which sensor node has too strong function, and the structure of network isnot flexible, and the model is designed for special application. Because the modelsare not designed much fit, the algorithms based on these models are not fit forgeneral application. Based on the analysis, a definition of standard WSNs model isproposed for general application. In this model, the function of sensor node is as far as possible weakened: the node can not locating its position by itself, and the allnodes’ coordinate system is not union when deployed, and the initial state of allnodes are same; and the network topology is not restricted: all nodes of WSNs aredeployed in a random way, and there are not anchor nodes in WSNs; and theboundary of different network protocol is defined clearly: the conflict oftransmission channel should be solved by MAC protocol, and The physical layercontrols the transmitting power information.2. A high efficient anchor-free node positioning algorithm is proposed basedon the general WSNs model. Its function is to activate the sensor nodes randomdeployed in the sensing area, and then to locate their position. There are two parts ofcontent of designing locating algorithm: the first is to transform the WSNs structureto the theory of global rigidity, and then to judge the feasibility of locating algorithm,and then to achieve the precondition of locating nodes; and the second part is todesign an anchor-free locating algorithm: the sink node is the start of locating, andthe wireless signal attenuation is used to calculate the distance between nodes andthe antenna array is used to get the angle of nodes, and then under the conditionsatisfying global rigidity, all sensor nodes are located by the method of ladderdiffusion. Based on the accurate positioning of the nodes, the algorithm does notcarry out the broadcasting operation from all nodes except sink node, so the energyconsumption in this phase is much conserved.3. Based on the node positioning algorithm, an energy efficient routingalgorithm is proposed to be answer for finding route from source node to sink nodeand maintaining the route. This energy efficient routing algorithm is designed basedon the clustering method which is improved from classic HAC by the means that thenodes residual energy is considered when clustering. And then a semi-staticclustering routing algorithm is proposed. In this algorithm, all sensor nodes shouldbe clustered at first by improved HAC method, and then the cluster head of eachcluster would be elected according to the node’s residual energy and communicationcost to other nodes in same cluster, and when rotating the cluster head, the nodes incluster would be elected but not re-clustering all nodes, and if there are some nodes’residual energy is too little, the re-clustering phase would be carried out. To ensurethe nodes’ residual energy information accurate, special data packet head is designedand a list of nodes in cluster is proposed. When data is transmitting, the data packethead would be used to update the information in nodes list to ensure this informationreal-time and accurate. According to the theory analysis and provement and simulation experiment, this algorithm has solved the “hot spot” and “energy hole”problems in WSNs, and it has high energy efficiency.4. Based on the clustering routing algorithm, an efficient data aggregationalgorithm is proposed. In data aggregation, the method of improving informationfiltering efficiency includes two parts: optimization the filter point deployment inWSNs and improving the efficiency of information filter technique. In this paper, themode of information filter is mended from the method based on buffering timebefore relaying to build a previous information queue to judge the redundant data. Inthis mode, the filter point in WSNs needs to build a dynamic queue, and the relayinginformation recent would be stored in this queue, and the content of queue should bedynamically updated when new information arriving to the filter point. And tooptimize the deployment of filter point, they would be attached in cluster head nodes,and their information queue’ length should be decided according to the distancebetween cluster head to sink node, and the queue’s length would be changed with theinformation transmitting: if there are more data to be relayed, the queue’s lengthwould be added, otherwise it would be reduced. By our data aggregation algorithm,the real-time of transmitting is ensured, and the accurate and entire of filteringinformation is improved too, and the dynamic queue’s length eases the nodes storageburden. In a word, this algorithm has high efficient in data aggregation, and reducethe redundant data transmitting, so much node’s energy is conserved.Although three different algorithms are proposed in this paper for three phasesof WSNs routing, these algorithms have same target to improve the energy efficiencyto prolong the network’s lifetime. So they can be integrated as a whole: the nodelocating algorithm is the first one, and its input is inactivated nodes random deployedin sensing area, and the output of this algorithm is the nodes set which has know itsand adjacent nodes’ position; and the routing algorithm is the second one, and itsinput is the result of locating algorithm, and the output is the optimized nodes’ setand the method of finding and maintaining route; the last is data aggregationalgorithm, and its input is the result of routing algorithm, and the output is the finalinformation arriving to sink node.In general, some overall analysis for WSNs routing is made in this paper, andaccording to the characters of different routing phase after WSNs deployed, the keyproblems should be solved to improve energy efficiency has been introduced indetail. And for each phase of routing, there is a corresponding high efficientalgorithm proposed, and all algorithms are integrated to improve WSNs energy efficiency overall. And all algorithms’ efficiency has been proved by theory and byexperiment in which the real environment and working condition of WSNs is wellsimulated.