Paper Menu >>
Journal Menu >>
![]() Wireless Sensor Network, 2010, 2, 718-723 doi:110.4236/wsn.2010.29087 Published Online September 2010 (http://www.SciRP.org/journal/wsn) Copyright © 2010 SciRes. WSN Opportunistic Routing for Time-Variety and Load-Balance over Wireless Sensor Networks Nan Ding, Guozhen Tan, Wei Zhang Department of Computer Science, Dalian University of Technology, Dalian, Liaoning, China E-mail: {dingnan,gztan}@dlut.edu.cn, wesley.cheung@163.com Received June 28, 2010; revised August 2, 2010; accepted September 4, 2010 Abstract To aware the topology of wireless sensor networks (WSN) with time-variety, and load-balance the resource of communication and energy, an opportunistic routing protocol for WSN based on Opportunistic Routing Entropy and ant colony optimization, called ACO-TDOP, is proposed. At first, based on the second law of thermo-dynamics, we introduce the concept of Opportunistic Routing Entropy which is a parameter repre- senting the transmission state of each node by taking into account the power left and the distance to the sink node. Then, it is proved that the problem of route thinking about Opportunistic Routing Entropy is shown to be NP-hard. So the protocol, ACO-TDOP, is proposed. At last, numerical results confirm that the ACO-TDOP is energy conservative and throughput gainful compared with other two existing routing protocols, and show that it is efficacious to analyze and uncover fundamental of message transmission with Opportunistic Routing in wireless network using the second law of thermodynamics. Keywords: Wireless Sensor Network, Load-balance, Time-variety, Opportunistic Routing Entropy 1. Introduction MULTI-HOP wireless networks, the same as mobile Ad hoc networks and wireless mesh networks, is considered to be convenient and cost-effective solutions in many important areas, such as traffic monitoring, environ- mental monitoring, and military security. Due to effects of multi-path fading, signal interfering and path losses, the link of WSN is time-varying. Besides, the power and working state of each node is time-varying, too. So the key challenge of multi-hop wireless networks protocol is ensuring that the “best” receiver of each packet forwards it. At present, most of the traditional multi-hop routing protocols in WSN typically adopt routing schemes and techniques similar to those in wired networks [1]. The protocols, such as DSR, OLSR, AODV and LEACH, have proposed to update the network routing periodically in order to adapt to the change of network, but messages are still transmitted through static routing. These meth- ods can partly solve the problem of energy consumption balance; however they cannot solve the dynamic changes of the link which is caused by the time-variety of the network [2]. The opportunistic routing which is proposed in recent years is a new dynamic routing based on multi-hop. It proposes a transmission method based on the opportunistic, that is, next relay is selected dynamically for each packet and each hop. Through a large number of experiments [3-6,7], they have verified the rationality and practicality of the opportunistic routing compared with traditional route in the network traffic process. To ensure the reli- ability and validity of the dynamic transmission network, the key of opportunistic routing algorithm is how to select the next hop node. Currently, there are two re- searching aspects on opportunistic routing: One aspect is to establish best routing for wireless network [8,9]. This aspect primarily builds the shortest path or near the approximate shortest path to improve the network throughput performance. Kai Zeng et al. [10] set up an optimization model for the throughput of the op- portunistic routing through a combination of graph theory and network flow theory. The other aspect is on the balance of energy consump- tion in opportunistic routing [11-13]. Lakshmi V. et al. [14] proposes two opportunistic transmission strategies referring to energy, one of which is to eliminate the nodes whose residual energy is less than threshold during establishing the transmission path dynamically, and the ![]() N. DING ET AL. Copyright © 2010 SciRes. WSN 719 other is that the network nodes are divided into concentric ring-type structure while the receive node as the center. With the latter strategy, when the message is sent to the ring whose nodes are close to the sink node, it will con- sider the residual energy to make the distribution of en- ergy consumption reasonable. According to the studies above, the network transmis- sion throughput rate and the energy balance are the key factors of dynamic establishment of opportunistic routing, and they are interactional and interdependent. For exam- ple, in order to achieve maximum network throughput rate and minimum delay, it is necessary to establish the shortest path, while the shortest path will lead to unbalanced energy consumption of the network. On the contrary, in order to balance the energy consumption within the net- work, packet transmission will avoid some node which is on the shortest path but has little energy left, which will increase the number of hops of packet transmission, in- creasing the time delay and reducing the network throughput rate. To coordinate these two factors, some scholars have proposed to use the opportunistic routing which is mainly to use heuristic algorithms, such as ant colony algorithm, to get the transmission path selection strategy [12,15]. But at present, we lack the optimization model and analysis methods of transmission routing based on time-varying characteristic, which is necessary for improving the performance of opportunistic routing, and the theory related with static networks is unable in the time-varying networks [16]. To solve the problem, this paper gives the data transfer rule that refers to the residual energy of the node and the shortest path of the network, based on the second law of thermodynamic. 2. Problem Formulation Taking into account the shortest path and energy balance with the time-varying characteristics of the network, we propose Opportunistic Routing Entropy which provides a theoretical basis for using opportunistic routing to create dynamic data transmission path. And we prove that it is a np-hard problem to get the best path which is time- varying and opportunistic. 2.1. Network Model and Assumptions This article assumes that nodes in the network are dis- tributed randomly in a rectangular area, and there prop- erties as follows: 1)Within the network, the unique sink node is deployed in the center of the area, the rest of sen- sor nodes will not move any more after deploying, and the location information of each node is unknown. 2) The identity of each node is unique. 3) The status of each node is equal, with the same computing and communica- tion capabilities, as well as initial energy. Combining the properties above, the network model is defined as follows: Definition 1 Network communication diagram. The communication graph of an N-node wireless sen- sor network is an undirected graph, G(V,E). V is the set of communication node, and V= Ssink∪Ssensor, where Ssink is the sink node and Ssensor is the set of sensor nodes. Each sensor node has a fixed communication range, R. dij is the distance between node i and node j. E is the set of edges and E = eij(i,jV) , dij ≤ R. Definition 2 Communication distance. In graph G, the communication distance is D(o, s) which value is the hop count between node o and node s. Definition 3 Set of neighbor node. The set of neighbor node is N(u), and N(u) = ni(niV, euni E), which includes the nodes which could commu- nicate directly with node u. Theorem 1 In WSN, the shortest path problem based on time-varying and the opportunistic method for trans- mission is shown to be NP-hard. Proof. With the opportunistic method, the nodes of WSN could choose the best link to repeat the messages considering the condition of current network. Even though the same node sends two messages in succession, it may take different paths for transmission these two messages, if conditions of the network transmission link changed, for example interference etc. And the latter message may arrive earlier than former. So the WSN transmission link working in the oppor- tunity method is NO-FIFO, when thinking about the time-varying characteristics of communication links. Ariel Orda et al has proved that in the time-varying net- work, if the communication link is NO-FIFO, its com- plexity of the shortest path problem is NP-hard. There- fore, in Opportunistic Routing, the shortest path problem based on time-varying is shown to be NP-hard [16]. 2.2. Opportunistic Routing Entropy and Programming The second law of thermodynamicshe (also called en- tropy law) developed by Rudolf Clausius, is the essential theory of thermodynamic. Entropy indicates that the sys- tem develop to the internal stable state without external interference. The greater the entropy is, the more stable the system is. Because nodes of WSN require the separate power supply as well as independent operation on normal con- ditions, its data packet transmission is in a relatively in- dependent system. Nodes will consume their energy during the data packet transmission process. In order to ![]() N. DING ET AL. Copyright © 2010 SciRes. WSN 720 balance the energy consumption of each node to extend the network lifetime, we should choose the node with more residual energy, less energy consumption and shorter number of hops from the sink node as the next hop. Therefore, according the second law of thermody- namicshe and the data packet transmission process in the time-varying network model, we have defined the Op- portunistic Routing Entropy and established the optimi- zation model. Definition 4 Opportunistic Routing Entropy. Opportunistic Routing Entropy, Sop, is the measure of transmission state of each node in WSN. Referred to as Shannon entropy, Sop cannot decrease too. It is given by (1). The more Sop, the less energy left and the more hops to sink node. () () () op u u op h wt SEt ut, (1) In (1), hu is the hop count between nodes u and the sink node, wu(t) is the weight that node o communicates with node u which is in neighbor node set N(o) of node o at moment t. Eop(t) is residual energy, which can be cal- culated by A/D converter in real time. During data transmitting, it will choose the node with small Opportunistic Routing Entropy as data forwarding node, and the Opportunistic Routing Entropy of this forwarding node will be progressively larger. Sop is on behalf of the probability of each node to be selected as next hop during data transmission. Smaller Sop is, more probability the node will be selected as next hop. Therefore, during forwarding the data, it will choose the neighbor node with small Sop as the next hop node. u u min .(,)() .. () () () () 0 (), ()0 () 0 1()0 0 (), 0 () () u u l l u op op l uu h Sut wt st Et Et Eu Eu wt wt h wt Et EtEt Et h (2) Referring to Theorem 1, it is shown to be NP-hard to get the shortest path of our model, so the problem of route thinking about Opportunistic Routing Entropy is also shown to be NP-hard. According to computational complexity theory, any np-hard problem do not exist completed algorithm within polynomial-time unless P = NP [17]. At present, there are two solutions to such problems, one is completed algorithm which can get the optimal solution but with high time complexity, and the other is to use heuristic algorithms which can only get the approximate optimal solution but within polynomial-time. As a result, we propose a heuristic algorithm based on ant colony opti- mization for the model which we establish. 3. ACO-TDOP Based on Ant Colony Optimization Ant colony optimization (ACO) takes inspiration from the foraging behavior of some ant species. Routing algo- rithms based on ACO algorithm have achieved good results in the network, especially in wireless sensor net- works. 3.1. Probabilistic Decision Rule of ACO Based on Sop When the source node o wants to send data, it will select the next hop node by following the random-proportional rule (see Equation(3)). It is a function thinking about the Sop and the amount of pheromone trail present on the connections between the nodes. So, it could choose the node with maximum value of P(j, t) as the repeat node. (,) (,) P, , (, ) () (, ) op iN op jt Sjt jtj N it Sit (3) where: P(j, t): the probability that the ant in the data packet move to node j at moment t. τ(j, t): the pheromone level of node j at moment t. Sop(j, t): the selection entropy of node j at moment t. N : the set of neighbors of the current node. β: a parameter which determines the relative influence of heuristic values Sop(j, t) (β > 0). 3.2. Pheromone Updating Rule When received the data packets from node u, node j will update its Pheromone τ(j, t). Introducing of the residual rate ρ(t) (Eqs.(6)), we have improved the existing calcu- lation model of pheromone. Pheromone τ(j, t) based on residual rate: , (),-1 jtt jt (4) u 1h ht (5) () ()=op init E t t E (6) ![]() N. DING ET AL. Copyright © 2010 SciRes. WSN 721 where ρ(t) is the pheromone accumulated parameter, which indicates the proportion of pheromone remaining at moment t. When the node has little residual energy, its residual rate ρ(t) is small and its evaporation of phero- mone is faster relatively. Einit represents of the initial energy of the node, and the initial energy of each node is fixed and equal in our model. hu is the hop count be- tween nodes u and the sink node. In Equation (4), τ(j, t) is the pheromone level of cur- rent node at moment t, and τ(j, t-1) is the pheromone level of current node at moment t-1. ∆τ is the new added pheromone, and in Equation (5),if the value of (hi - hj) is greater than zero, then it can conclude that node j is closer to the sink node than node i. Hence, the algorithm will reward the path from node i to node j by depositing more pheromones. If the value of (hi - hj) is equal to zero, then it means that both nodes i and j have the same hop count to the sink node. As a result, the algorithm will deposit the amount of pheromone τ(j, t) on the path. If the value is less than zero, the algorithm will not deposit pheromone on this path. 3.3. ACO-TDOP Algorithm Combining Opportunistic Routing Entropy with ant col- ony algorithm, we propose a new routing algorithm, ACO-TDOP, and Figure 1 presents its Working state diagram. The main process is as follows: 1) Initial state: Starting from the state, S0, initialize the system variable, and the sink node will flood the ini- tialization packet to all the nodes in the network firstly. After the node receives this packet, it will compute the hop count to the sink node. Figure 1. State machine of ACO-TDOP. 2) Ant waiting and information gathering: After initialization, the source node will enter the state S1 to wait to send ants. When the source node wants to send ants, it will send a request packet to each neighbor node, and wait for feedback messages from neighbors, that process is the state S2. During the waiting time T_collect, we will calculate the selection probability P(j, t) of each neighbor on the basis of feedback message, which in- clude Opportunistic Routing Entropy Sop and pheromone τ(j, t). After the waiting time T_collect, the node will enter to state S3. 3) Next hop node selection: We will select the node whose P(j, t) is largest among the neighbors in N as the next hop to send the ant. 4) Pheromone update: This is the state S4, and there are two kinds of mode which can be converted to this state. One mode is to update the Pheromone immediately after sending a message over, the other is that the pheromone will be evaporated when the node is idle for a period of time such as T_wait. If the residual energy of the node is less than the threshold ε, then the node will be die and close its communication so as not to transmit any information. 4. Simulation Results 4.1. Simulation Environment This experiment simulation environment is NS-2. For these simulation experiments, we assumed that there are 300 sensor nodes distributed randomly in a 300×300 square region. All nodes have the same transmission range. There is a single sink node located at coordinates (150, 150) of the wireless sensor networks, which re- ceives the data of all source nodes for all the simulations. The parameters of simulations are listed in Table 1. Simulation is mainly on two aspects, one of which is to compare the ACO-TDOP protocol with other routing protocols including traditional Ant Colony algrithm and EEABR on the performance, and the other is to get a dynamic path with ACO-TDOP protocol by tracking a packet from the source node to sink node. 4.2. Comparison with Other Protocols For the Simulation, we will compare ACO-TDOP algo- rithm with other two algorithms. The first is the routing algorithm based on traditional ant colony algorithm which is used to solve the approximate shortest route in [7] and [13], and the second is EEABR routing algorithm which is proposed in [11]. EEABR is also based on ant colony but refer to the energy in the route, which means ![]() N. DING ET AL. Copyright © 2010 SciRes. WSN 722 that if there is more energy in one path, the density of pheromone in this path will increases more and the path will have more chance to be selected. In the same simulation environment and net topology scale, we have done experiment for 100 times to com- pare the network lifetime of ACO, EEABR and ACO- TDOP algorithm. Network lifetime can be defined as the time elapsed until the first node (or the last node) in the network depletes its energy (dies). From Figure 2, we can see that ACO has shortest lifetime than others, and EEABR is shorter than ACO-TDOP. Because ACO- TDOP considers the left energy of each node in the path. In order to analyze the residual energy distribution of nodes at the end of WSN, we also have done test more than 100 times. As a result shown as Figure 3, EEABR and ACO-TDOP algorithm has a more balanced energy consumption of the network, and there are more than 80% of the nodes whose residual energy is less than 35% of the initial value. Figure 4 shows the comparison of the throughput rate after 100 tests. We can see that the throughput rate of BACO, EEABR and ACO-TDOP are quite similar to Table 1. Parameters of simulations. Parameters value Simulated area 300×300 Number of sensor nodes 300 Initial energy 50J Sink node location (150,150) Transmission range 25m Transmitter energy consumption 50×10-8J/bit Computing energy consumption 50×10-8J/bit Circuit energy consumption 50×10-8J/bit Figure 2. Lifetime of the networks. Figure 3. Distribution of Average Energy. Figure 4. Distribution of throughput gains. each other. As the test carry on, the BACO has a rela- tively stable throughput rate owing to without taking into account of energy consumption, while the throughput rate of EEBAR and ACO-TDOP is less than BACO for considering the residual energy of nodes. However, the throughput of EEBAR and ACO-TDOP is more than BACO, that is to say they make full use of the residual energy of the network, so they are better than BACO. 4.3. Path Tracking In order to verify that ACO-TDOP routing algorithm can dynamically adjust the transmission path, we have re- corded several dynamic paths between source node s and the sink node, as shown in Figure 5. We can see that the length of the path is only 10 hops at first, as the consump- tion of energy, the length of the path can reach to 16 hops. Y-Total Hop Count or Message Transmission in the Network X Number of messages X Ratio of Energy Left (%) Y Occupation Ration (%) N etwork Lifetime(time Units) ACO EEABR ACO-TDOP 57289 89713 97863 ![]() N. DING ET AL. Copyright © 2010 SciRes. WSN 723 Figure 5. Path formation to sink node from the first run to network lifetime. 5. Conclusions Based on the analysis of available opportunistic routing protocols, this paper analyzes and describes the message transmission process in the time-varying network model referring to the second law of thermodynamics, and pro- poses the Opportunistic Routing Entropy to replace the original entropy so as to indicate the network transmis- sion status of each node. Further, combining Opportunistic Routing Entropy and Ant Colony Optimization, this pa- per raises an opportunistic routing protocol, ACO-TDOP, for time-varying network model considering the load balancing of the network resources. So the message is ensured that the “best” receiver of each packet forwards it. At last, numerical results confirm that the ACO-TDOP is energy conservative and throughput gainful compared with other two existing routing protocols, ACO and the EEBAR opportunistic routing protocol. 6. Acknowledgments This paper was supported in part by the National Basic Research Program under No. 2005CB321904. 5. References [1] D. Tse and S. Hanly, “Multi-Access Fading Channels: Polymatroid Structure, Optimal Resource Allocation and Throughput Capacities,” IEEE Transactions on Informa- tion Theory, Vol. 44, No. 7, 1998, pp.2796-2815. [2] J. Lian, K. Naik and G. Agnew, “Data Capacity Improve- ment of Wireless Sensor Networks Using Non-Uniform Sensor Distribution,” Journal of Distributed Sensor Net- works, Vol. 2, 2006, pp.121-145. [3] S. Biswas and R. Morris, “ExOR: Opportunistic Multi- Hop Routing for Wireless Networks,” Proceeding of ACM SIGCOMM 05, ACM Press, Pennsylvania, pp. 133- 143, 2005. [4] H. F. Hu and Z. Yang, “Collaborative Opportunistic Routing in Wireless Sensor Networks,” Journal on Communications, Vol. 30, No. 8, 2009, pp.116-123. [5] C. Luk, W. Lau and O. Yue, “An Analysis of Opportunis- tic Routing in Wireless Mesh Network,” Proceeding of IEEE International Conference on Communications, Bei- jing, 2008, pp. 2877- 2883. [6] S. Flody, V. Jacobson, et al. “A Reliable Multicast Framework for Light-Weight Sessions and Application Level Framing,” IEEE/ACM Transactions on Networking, Vol. 5, No. 6, 1997, pp.784-803. [7] K. Zeng, W. J. Lou, et al. “Capacity of Opportunistic Routing in Multi-Rate and Multi-Hop Wireless Net- works,” IEEE transactions on wireless communication, Vol. 7, No. 12, 2008, pp. 5118-5128. [8] Y. Zhang, D. Lukas, et al. “Improvements on Ant Routing for Sensor Networks,” Lecture Notes in Computer Sci- ence, 2004, pp.154-165. [9] K. Zeng, W. J. Lou, et al. “On End-to-end Throughput of Opportunistic Routing in Multi-Rate and Multi-Hop Wireless Networks,” Proceedings of the IEEE INFOCOM, Phoenix, 2008, pp. 1490-1498. [10] J. N. Laneman and G. Wornell “Energy-Efficient Antenna Sharing and Relaying for Wireless Networks,” Proceed- ing of IEEE Wireless Communications and Networking. Chicago, 2000, pp.7-12. [11] T. Camilo, C. Carreto, et al. “An Energy-Efficient Ant- Based Routing Algorithm for Wireless Sensor Net- works,” Ant Colony Optimization and Swarm Intelligence, 2006, pp. 49-59. [12] J. Li and P. Mohapatra “Analytical Modeling and Mitiga- tion Techniques for the Energy Hole Problems in Sensor Networks,” Pervasive and Mobile Computing, Vol. 3, 2007, pp.233-254. [13] V. Lakshmi, Thanayankizil, Aravind Kailas, et al. “Two Energy-Saving Schemes for Cooperative Transmission with Opportunistic Large Arrays,” Proceedings of Global Telecommunications Conference, Washington, DC, 2007, pp.1038-1042. [14] S. Okdem and D. Karaboga. “Routing in Wireless Sensor Networks Using Ant Colony Optimization,” Proceedings of Adaptive Hardware and Systems, Istanbul, 2006, pp. 401-404. [15] M. Dorigo and V. Maniezzo Etal, “The Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Transaction on Systems, Man, and Cybernetics - Part B, Vol.26, No. 1, 1996, pp. 1-13. [16] A. Orda and R. Rom, “Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge- Length,” Vol. 37, No. 3, 1990, pp. 607-625. [17] M. R. Garey and D. S. Johnson, “Computers and Intrac- tability: a Guide to the Theory of NP Completeness,” Whfreemanand Company, New York, 1979. X Time Units ( /100 Time Units ) Hop Count to Sink Node |