J. Cent. South Univ. Technol. (2009) 16: 0265-0268

DOI: 10.1007/s11771-009-0045-z

A sink moving scheme based on local residual energy of nodes in wireless sensor networks

TAN Chang-geng(谭长庚), XU Ke(许 可), WANG Jian-xin(王建新), CHEN Song-qiao(陈松乔)

 (School of Information Science and Engineering, Central South University, Changsha 410083, China)

Abstract: In the application of periodic data-gathering in sensor networks, sensor nodes located near the sink have to forward the data received from all other nodes to the sink, which depletes their energy very quickly. A moving scheme for the sink based on local residual energy was proposed. In the scheme, the sink periodically moves to a new location with the highest stay-value defined by the average residual energy and the number of neighbors. The scheme can balance energy consumption and prevent nodes around sink from draining their energy very quickly in the networks. The simulation results show that the scheme can prolong the network lifetime by 26%-65% compared with the earlier schemes where the sink is static or moves randomly.

Key words: wireless sensor network; network lifetime; moving scheme; residual energy

1 Introduction

Wireless sensor networks usually compose of a large number of sensors that are deployed in the monitoring fields to sense the physical environments, and a few sinks that are involved in gathering data and communicating with the outside [1]. Wireless sensor networks can give real-time monitor to the local environment, gather and process the sensed data, and take actions when there is an emergency. It can provide diverse services to numerous applications, such as surveillance systems and control systems for commercial, industrial, and military scenarios [2]. Since sensor nodes are expected to be deployed in harsh environments, which cause great difficulty to recharge or change their battery, the lifetime of a wireless sensor network is limited due to the limited battery lifetime of the sensors. As a result, energy efficiency is a promising research field in wireless sensor networks.

There are many energy-efficient routing protocols proposed recently [3-5]. But if the sink is static, the sensors around the sink (called “hotspots”) will deplete energy so fast to death. Many researches have pointed out that introducing sink mobility can reduce the effect of the “hotspots” problem and improve network performance, including throughput, reliability and energy efficiency [6-8]. However, introducing sink mobility will bring about many difficulties to wireless sensor networks, such as the way to move, to stay or not and where to stay. At the same time, some moving schemes are not suitable for the data-gathering networks. Random moving scheme is unconscious of the energy and may aggravate the “hotspots” problem [9-11]. In addition, a mobile sink that moves along some predefined tracks lacks flexibility and scalability, and so its moving path always has to be redesigned when network is changed [12]. In contrast, if the sink node moves according to the current network situation, it will be much better in adaptability. AKKAYA et al [13] pointed out that finding the optimal location for the sink to stay is an NP-hard problem and proposed a heuristic algorithm to determine the moving directions and distances. In the algorithm proposed in Ref.[13], a sink moves towards the nodes that generate the most number of data packets, but it moves only when it detects an unacceptable performance. Therefore, the algorithm is more suitable for event-driven applications rather than data-gathering applications. VINCZE et al [14] proposed two strategies to move the sink adaptively to react to dynamic events that followed a correlated random walk mobility model, impracticable to the mobile devices that gather data periodically from all sensor nodes. BI et al [15] proposed a half-quadrant-based moving strategy (HUMS). The sink chooses the sensor node with the highest residual energy to stay, and avoid passing the hotspots that already have existed. But this strategy requires all the sensors to unpack every packet to find out the node with the highest residual energy and the lowest, it will deplete a lot of energy by doing so. Besides, this strategy does not take the residual energy of neighbors into account. If some neighbors are in energy crisis, they are also a potential threat to the network.

2 A sink moving scheme based on local residual energy of nodes

In the paper, a moving scheme for sink nodes based on the local residual energy of nodes is presented. Let C_i be the number of neighbors of node i and E_i be the average residual energy of node i and its neighbors.

2.1 Network model

Wireless sensor network which is used for periodic data-gathering has the following characters.

(1) It consists of a large number of sensor nodes with limited energy and one sink with unlimited energy.

(2) Each sensor node has a unique pre-configured ID.

(3) Sink can move anywhere without limitation, and all sensor nodes are reachable.

(4) Sensors and sink are all equipped with GPS system.

(5) Each sensor generates one packet in each data-gathering period.

(6) The transmission range of sensor nodes and sink are fixed and the sink’s transmission range is larger than that of sensor nodes.

(7) The energy consumption for transmitting one bit is fixed and forwarding data is the most energy depletion activity.

For building a neighbor-list in each sensor node, it broadcasts a HELLO message to its neighbors, which includes its own ID. HELLO messages are sent with different random delays to reduce local collisions. Sink does not send or receive any message during this process.

After the neighbor-list is built, the network can start to generate and gather data. In every data-gathering period, packets are sent to sink through multi-hop way. Sink makes a moving decision periodically and moves to there directly.

2.2 Local maximum residual energy moving scheme

The local maximum residual energy moving scheme (LMREM) consists of the following three steps.

(1) Sensors send their packets to sink through multi-hop routing when sink is static. Sink keeps static for T_stay time during the phase which it gathers data from other sensor nodes. At this phase, many existing energy-efficient protocols designed for static networks could be applied. After a T_stay time, sink broadcasts a STOP message to sensor nodes. Sensors that received this message stop sending packets at once and buffer the packets both generated by its own and received from other nodes, then go to sleep.

(2) The sink chooses a position in the range of its transmission radius (R_sink) to stay. As the transmission radius of sink is fixed, the moving time T_move will not be long. The most important thing is that we should make sure T_stay>>T_move.

(3) After the sink arrives at the destination, all the sensor nodes will be woken and a routing update information is launched. Then a new data-gathering phase starts.

The position of the sink has more effect on the performance of wireless sensor network, especially on the energy consumption. So how to choose a new position for the sink to stay is very important in data- gathering. In the paper, a new parameter, named stay- value, is given to evaluate the position i, which is defined as Formula (1).

P_i=αE_i+βC_i                                  (1)

where  α and b are priority factors, and α+b=1. Both the local residual energy and the number of neighbors are taken into account for computing the stay-value of position i. It is clear that the larger is the stay-value of position i, it is more feasible for the sink to stay. In LMREM, the position with the maximum stay-value will be chosen as a new position for the sink.

Before choosing a new position, the sink broadcasts a request message for obtaining the value of E_i and C_i of each sensor node which locates its transmission range. For each sensor node i that receives the message, it will compute its own E_i by obtaining the residual energy of its neighbors. Then it will return a message including its own E_i and C_i to the sink. The format of the message is shown in Fig.1.

Fig.1 Format of message for sensor node i

After the sink receives messages from all sensor nodes locating in its transmission range, it can compute P_i according to Formula (1). If the value of P_i for current position is higher than that of any other ones, it will remain static in the next data-gathering period; otherwise it will move to the position with the highest P_i. When the number of nodes with the highest P_i is more than one, the sink will choose the node which is the furthest among these nodes as the new position. In this way, the energy consumption among local nodes can be balanced effectively. The distance d between the sink and sensor node i can be computed as follows:

               (2)

where  x_sink and y_sink are the positions of the sink; x_i and y_i are the positions of sensor node i.

3 Simulation results

3.1 Simulation environment

The simulation was performed in NS2. We adopted the TwoRayGround propagation model, employed the 802.11 as the MAC protocol with the rate 2 Mb/s, and combined the moving scheme with the AODV routing protocol. Sensors were randomly distributed in a 1 000 m×1 000 m area. The transmission and receiving powers are 14.8 and 12.5 mW per bit. All sensors are static and their initial energy is 50 J. Sensors generate a packet every 5 s with the same length of 512 bytes. Sink is deployed at the center of the network at the beginning of the simulation.

3.2 Performance evaluation

(1) Packet success delivery rate: the proportion of the packets received by the sink to all generated.

(2) Network lifetime: the period from the beginning of the network to the first sensor node dies.

(3) Average delay: the average delay of all packets received by the sink.

3.3 Experimental results and performance analysis

We evaluated the performance of the LMREM by comparing with the static sink and the random moving strategy in terms of the packet success delivery rate, lifetime and average delay.

We first examine the effect of the node densities. The comparison of the network lifetimes by the three strategies is shown in Fig.2. Compared with the static sink, all the other strategies can extend the network lifetime, and LMREM achieves a much better performance than the random moving strategy. LMREM can extend the network lifetime up to 26%-65%. As the node density increases, the network lifetime of each strategy decreases, because the more the sensors are, the greater the amount of data generated and gathered. Moreover, when the density is low, the static sink achieves higher performance than the random moving strategy, for the random movement causes more routing breakup and rebuilding while receiving packets. As the density increases, the hotspots become the bottleneck of the static sink. LMREM dose not receive data while the sink moves to the energy-efficient location, and all sensors switch to sleeping when the sink moves, thus achieving the best performance among all the presented strategies. In contrast with LMREM, the random movement is completely energy-unconscious, which causes a lot of overheads in continuous routing failure and rebuilding when the traffic is high.

Fig.2 Network lifetime with different node densities

Although mobility brings energy balance to all the sensor nodes, it also causes some problems such as collisions, delays, and routing rebuildings. Fig.3 shows that the static sink achieves the best success delivery rate among all strategies with the support of the AODV because the sink is static and the routing protocol works very well. Sensors will　stop sending packets and buffer them while sink moves in the LMREM, which will cause a packet drop while traffic is high and the buffer is limited. But the most important thing is that all the current routing protocols in wireless sensor networks for the static sink can be supported by LMREM unconditionally. In random sink movement, sink collects data while moving, which will cause a lot of route failures and routing rebuildings. So a lot of packets are lost when the traffic is high.

Fig.3 Success delivery rate with different node densities

There will be more packets waiting in the interface queue while the traffic is high, so the average delay of each strategy increases as the density grows, as shown in Fig.4. Because of the periodic mobility and data unconsciousness while the sink moves, the LMREM has a higher average delay among all the strategies when the traffic is low. As the density grows, the proportion of the packets waiting in the interface queue decreases, the sink movement decreases. At last, the performance of LMREM is better than that of random moving strategy when the number of nodes is more than 350.

Fig.4 Average delay with different node densities

4 Conclusions

(1) Energy efficiency is significant in wireless sensor networks with energy-constrained nodes. This work explores the idea of exploiting the mobility of data collection points (sinks) for the purpose of increasing the lifetimes of wireless sensor networks. A LMREM moving scheme for sensor networks with a mobile sink is proposed. The LMREM scheme not only fully uses of the sensors around the sink with high residual energies to relay data generated by the networks, but also takes the number of neighbors into consideration to avoid exhausting the neighbors with low remaining energy. This results in a fair balancing of the energy depletion among the network nodes. Besides, all the current routing protocols in wireless sensor networks for static sink can be supported by LMREM unconditionally.

(2) In contrast to the schemes of the static or randomly moved sink, the experimental results show that LMREM can extend the network lifetime up to 26%-65% with an acceptable network performance in terms of the transmission rate and delay.

References

[1] CALLAWAY E H. Wireless sensor networks: Architectures and protocols[M]. Boca Raton, FL: Auerbach Publications, 2003.

[2] ZHOU Xuan, YU Shou-yi. Optimal sensor location for the parameter identification in the distributed parameter system [J]. Journal of Central South University of Technology: Natural Science, 2004, 35(1): 97-100. (in Chinese)

[3] SOHRABI K, GAO J, AILAWADHI V. Protocols for self-organization of a wireless sensor network [J]. IEEE Personal Communications, 2000, 7(5): 16-27.

[4] AI-KARAKI J N, KAMAL A E. Routing techniques in wireless sensor networks: A survey [J]. IEEE Wireless Communications, 2004, 11(6):6-28.

[5] NICULESCU D. Communication paradigms for sensor networks [J]. IEEE Communications Magazine, 2005, 43(3): 116-122.

[6] WANG W, SRINIVASAN V, CHAING K C. Using mobile relays to prolong the lifetime of wireless sensor networks [C]// Proceedings of the 11th Annual International Conference on Mobile Computing and Networking(MobiCom’05). New York, NY, USA: ACM Press, 2005: 270-283.

[7] WANG G L, CAO G H, PORTA T L. Sensor relocation in mobile sensor networks [C]// Proceedings of the 24th Annual Conference of the IEEE Computer and Communications Societies (INFOCOM’05). Piscataway, NJ, USA: IEEE Press, 2005: 2302-2312.

[8] LUO J, HUBAUX J P. Joint mobility and routing for lifetime elongation in wireless sensor networks [C]// Proceedings of the 24th Annual Conference of the IEEE Computer and Communications Societies (INFOCOM’05). Piscataway, NJ, USA: IEEE Press, 2005: 1735-1746.

[9] SHAH R C, ROY S, JAIN S, BRUNETTE W. Data MULEs: Modeling a three-tier architecture for sparse sensor networks [C]// Proceedings of the 1st IEEE International Workshop on Sensor Network Protocols and Applications (SNPA’03). Piscataway, NJ, USA: IEEE Press, 2003: 30-41.

[10] TONG L, ZHAO Q, ADIREDDY S. Sensor networks with mobile agents [C]// Proceedings of IEEE Military Communications Conference (MILCOM’03). Piscataway, NJ, USA: IEEE Press, 2003: 688-693.

[11] JAIN S, SHAH R C, BORRIELLO G. Exploiting mobility for energy efficient data collection in sensor networks [J]. Mobile Networks and Applications, 2006, 11(3): 327-339.

[12] GANDHAM S R, DAWANDE M, PRAKASH R. Energy efficient schemes for wireless sensor networks with multiple mobile base stations [C]// Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM’03). Piscataway, NJ, USA: IEEE Press, 2003: 377-381.

[13] AKKAYA K, YOUNIS M, BANGAD M. Sink repositioning for enhanced performance in wireless sensor networks [J]. Computer Networks, 2005, 49(4): 512-534.

[14] VINCZE Z, VASS D, VIDA R, VIDACS A, TELCS A. Adaptive sink mobility in event-driven multi-hop wireless sensor networks [C]// Proceedings of the 1st International Conference on Integrated Internet Ad Hoc and Sensor Networks (InterSense’06). New York: ACM Press, 2006: 13-22.

[15] BI Yan-zhong, SUN Li-min, MA Jian, LI Na, KHAN I A, CHEN Can-feng. HUMS: An autonomous moving strategy for mobile sinks in data-gathering sensor networks [J]. EURASIP Journal on Wireless Communications and Networking, 2007, 2007: 64574.

Foundation item: Project(60673164) supported by the National Natural Science Foundation of China; Project(20060533057) supported by the Specialized Research Foundation for the Doctoral Program of Higher Education of China

Received date: 2008-06-28; Accepted date: 2008-09-25

Corresponding author: WANG Jian-xin, Professor; Tel: +86-731-8830212; E-mail: jxwang@mail.csu.edu.cn

(Edited by YANG You-ping)