Optimal Location through Distributed Algorithm to Avoid Energy Hole in Mobile Sink WSNs

Abstract

In multihop data collection sensor network, nodes near the sink need to relay on remote data and, thus, have much faster energy dissipation rate and suffer from premature death. This phenomenon causes energy hole near the sink, seriously damaging the network performance. In this paper, we first compute energy consumption of each node when sink is set at any point in the network through theoretical analysis; then we propose an online distributed algorithm, which can adjust sink position based on the actual energy consumption of each node adaptively to get the actual maximum lifetime. Theoretical analysis and experimental results show that the proposed algorithms significantly improve the lifetime of wireless sensor network. It lowers the network residual energy by more than 30% when it is dead. Moreover, the cost for moving the sink is relatively smaller.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Li Qing-hua 1,2 and Gui Wei-hua 1 and Chen Zhi-gang 1

Academic Editor:N. Barsoum and Academic Editor:V. N. Dieu and Academic Editor:P. Vasant

1, School of Information Science and Engineering, Central South University, Changsha 410083, China
2, Institute of Technology, Lishui University, Lishui, Zhejiang 323000, China

Received 2 January 2014; Accepted 20 February 2014; 7 May 2014

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Wireless sensor networks are a self-organizing network composed of random distribution of intensive, low-cost, integrated sensors with the function units of sensing module, data-processing module, and short-range wireless communication module. By the measurement the surrounding environment such as humidity, temperature, heat, infrared, sonar, radar, and seismic waves with a variety of built-in sensors to sensor network has achieved a full range of monitoring and controlling the physical world. It is an important integral part of long-term planning of next generation Internet and has already been widely used in the past few years [1].

Sensor nodes usually cannot be replaced or reallocated energy in wireless sensor network, and most applications need to ensure long-term monitoring of certain areas (most applications have prespecified lifetime requirements); for example, the application mentioned in [2] requires that the effective monitoring time for the network should be greater than 9 months to extend the life of sensor network and, thus, is of great significance.

However, research to improve the network life is of great challenges. There is a sensor network-specific "energy hole" phenomenon, which refers to premature death of those nodes in the hotspot. In multihop data collection sensor network, nodes near the sink have to suffer more routing load [3], so the energy consumption level is higher than nodes in other regions. This is known as the hotspot. Study shows that because of the impact of the energy hole, the network residual energy is as high as 90% [4] when the network is out of function.

Different from the general network with static sink, intelligent mobile robots can act as a mobile sink in the network to collect data. When the residual energy near the sink becomes small, sink repeatedly moves to the location with more abundant remaining energy so as to achieve a balanced energy consumption rate among the entire network, avoiding the energy hole and obtaining longer network lifetime.

Despite a lot of research on the mobile sink, different from previous studies, the main contribution of this paper is as follows.

(1) Many researchers recognize the existence of hotspots near the sink, so mobile sink strategy is to move sink to the areas with the highest remaining energy in order to avoid energy hole near the sink and achieve the purpose of balance energy consumption. According to our study, when the sink is seated at different locations in the network, power consumption near sink is of different sizes. Energy consumption in different directions is also not the same. In many cases (especially when the sink is at the edge of the network) the power consumption in network-centric side of sink is much higher than the other side near the edge of the network. Meanwhile, on the side near network-centric, even energy consumption in regions far from the sink is higher than that of the near-edge side. Consequently, simple conclusion is that "areas near sink" which have higher energy consumption cannot effectively guide the design of sink mobility, and they are too general and difficult to be implemented in practice.

In this paper, through differential analysis, precise energy consumption of each node, for the first time, is given for arbitrary sink location in the network. This lays the foundation for mobile sink and energy balancing strategy.

(2) We propose distributed sink mobile strategy. Based on theoretical analysis of network energy consumption, it can estimate the power consumption of the network before sink moves to the new anchor and predict the optimal next location for sink according to the actual energy consumption of current network. In addition, previous studies fail to present a good solution to the cost of the sink migration. The distributed strategies proposed in this paper are different from previous studies. As the sequence of sink anchors does not affect the ultimate energy consumption and network lifetime, we usually do not move sink according to the calculated result. Instead, we compute a couple of anchors prior to moving and then traverse all the locations according to the minimum moving cost in each step in order to minimize the total cost.

The organization of this paper is as follows. Section 2 introduces relevant research. The network model and the problem statement are presented in Section 3. Section 4 introduces characteristics of data forwarding and energy consumption. It is the basis of theoretical research of our paper. Section 5 describes distributed sink mobile strategy. Section 6 discusses performance and experimental comparison. Section 7 is a summary of the whole paper.

2. Related Work

There are many existing researches handling energy hole problem. They can be divided into two categories based on the sink mobility: static sink network (for short, static sink) and mobile sink network (for short, mobile sink). Although this paper focuses on mobile sink, solutions to avoid energy hole in static sink can often be used here. Therefore, we first introduce related research with static sink.

(a) Analysis and evaluation model. Li and Mohapatra [5] first propose a mathematical model to analyze the energy hole problem. They assume that the network is uniformly distributed in a circle network and then analyze and compare performance of several existing strategies to avoid energy hole from the perspective of network traffic [6]. They point out that hierarchical structure and data compression mechanism are effective for alleviating the energy hole problem, increasing the rate of data collection, in turn, exacerbating the energy hole [5] and effectiveness of increasing number of the nodes is not obvious.

(b) Node density control strategy. The principle is that the higher energy consumption near the sink causes the energy hole problem, and therefore it is effective to deploy more nodes near the sink in order to reduce the data load of every node, alleviating the impact of energy hole. This is the so-called nonuniform distribution strategy. Another manifestation of node density control strategy is to deploy more nodes in the place where hotspots are possible to appear which is also effective. Such studies can be found in the literature [7-9].

(c) Adjustable sensing and communication range. The main principle of this type of strategy is that the node transmission power is adjustable; for example, Berkeley Motes node has 100 transmission power levels [10]. Node energy consumption is directly proportional to α power of transmission distance and therefore uses smaller transmission range in hotspots near sink and larger transmission range in regions far away from the sink which can achieve balanced energy consumption. This strategy can be combined with node density control strategy. For example, Hossain et al. [11] set the interval between nodes near the sink smaller so that the required energy to transmit data is small, set the interval between nodes far away from the sink larger, so the required energy to transmit data is larger. In this way, it can achieve balanced energy consumption among all of the nodes. Such studies can be found in the literature [12, 13].

The above discussion is under the situation where sink is stationary after deployment. However, with the development of intelligent robot, the research of mobile sink has attracted more and more attention [14]. The research in mobile sink can be summarized into the following categories.

(a) Relay nodes: such method is to use relay node in hotspot to avoid energy hole. Relay nodes can be both stationary and mobile. The role of mobile relay nodes is essentially similar with that of mobile sink. Related research can be found in the literature [15, 16].

(b) Single mobile sink: in this kind of networks there is only one sink, and it is movable. Luo and Hubaux [17] propose an early solution for mobile sink to solve the unbalanced energy consumption. As the sink can move, the nodes around it keep on changing over times, and thus it can avoid energy hole around the sink. The author proves that in a circular sensor network, putting sink in the center of a circle is the best way to save energy. Also, he claims that sink moving along the edge of the network can achieve minimum energy consumption.

Luo also puts forward a strategy that mobile sink moves along the anchor (anchor points) to collect data in [18]. The main idea is that when the sink stays in an anchor it collects data and gets the situation of energy consumption over the whole network in order to determine the interval to stay in every anchor.

As the energy consumption rate near the sink is relatively higher, [19] analogizes sink as "lawn" (mower) and the region with higher remaining energy as "grass" where relatively higher. So the strategy of moving the sink is the "lawn" (mower) moving to the region where "grass" is relatively higher repeatedly.

Reference [20] presents a mobile sink trajectory optimization algorithm and the main idea is as follows. At first, the mobile sink moves along a straight line and collects information about network data and energy consumption information. Mobile sink then adjust the trajectory using the latest information which collected in the process of data collection so that the mobile sink moves near the nodes in order to reduce the cost of data communication and thus to form an optimal trajectory of sink. The paper discusses random movement, forecast movement, and the network performance of different nodes of data collection patterns (passive, multihop, and limited multihop). Reference [21] sums up the target of mobile sink strategy into three categories: (1) minimizing average energy consumption; (2) minimizing largest energy consumption; (3) minimizing relative energy consumption and proposes corresponding mobile algorithms. More research on single mobile sink can be found in [22-24].

(c) Multiple mobile sinks: compared with single mobile sink, multiple mobile sinks will increase the cost of the network, but the network performance (network lifetime, network delays) can be greatly improved and, therefore, is subject to a wide range of research. However, mobile sinks require mutual cooperation and mutual coordination of movement between several sinks, and thus the study is more complicated than research of single mobile sink.

The latest research about multiple mobile sinks can be found in [24] which studies the optimization strategy of multiple mobile sinks and compares the situations of a number of stationary sinks and sinks moving along the hexagon surrounding. They find that sink mobility can significantly increase the network life, and the more points sink stays along the hexagon surrounding, the better balanced energy consumption the network will achieve. Mirela Marta, finally, proposes the distributed mobile optimization algorithm to maintain connectivity between the mobile sinks. Related research about multiple mobile sinks can also be found in [23, 24].

In addition, whether the research handles single or multiple mobile sink, they may adopt different strategies for data collection. It can be summed up in two circumstances. One is that mobile sink and static sink adopt the same type of data collection, using a static network sophisticated data collection strategies, such as single-hop, multihop, and subcluster. The other is to use different type data collection strategies from static sink, such as sensor nodes cache data so that the data is sent to sink when it arrives at vicinity of sensing, or the data is sent to a fixed regional cache, and then sink moves along the fixed region to collect data.

3. Network Model and Problem Description

Network architecture model: we apply the module similar with [17, 19], a typical wireless sensor network for cyclical data collection and a circle with radius of R ; see Figure 1. In this network, there are n nodes and, {_N0 ,_N1 ,_N2 ,_N3 ,..._Nn }, _N0 stands for sink and it can move throughout the network; others represent work nodes and cannot move after initially deployed. Communication range of nodes is noted with r ; the difference from general sensor networks is that the transmission range is adjustable, and nodes automatically adjust its communication range based on the distance between two nodes; for example, Berkeley Motes node has 100 transmission levels [7, 19]. Each work node will sense data in each cycle. We use the mature shortest path protocol for collecting data [8] and sending them to sink with multihop [8, 9].

Figure 1: Network architecture model.

[figure omitted; refer to PDF]

Energy consumption model: we use typical energy consumption model; the cost of moving mobile sink is calculated according to formula (1), cost for sending data is calculated according to formula (2), cost for receiving data is calculated according to formula (3), and specific details can be found in the literature [14]: [figure omitted; refer to PDF] where _Eelec stands for the energy loss of firing circuit. If the transmission distance is less than the threshold _d0 , power amplifier loss is based on free-space model; when the transmission distance is greater than or equal to the threshold value, it uses multipath attenuation model. _{[straight epsilon]fs} , _{[straight epsilon]amp} represent the power for these two models' amplification, respectively. Energy for receiving l bit of data refers to formula (3). In this paper, the above specific parameters come from the literature [14].

Problem Description . For a given mobile sensor network shown in Figure 1, the problem can be described as follows: how to move and choose the anchors of mobile sink to maximize the network lifetime? Here we term the rounds of data collection till the first node dies as the network lifetime [7, 14].

4. Analysis Load of Node and the Tactor That Affects the Network Lifetime

4.1. Analysis Load of Node

When the sink moves to an arbitrary location such as (_x0 ,_y0 ), if it is able to calculate the data load of each node, it then will be easy to calculate the energy consumption of each node based on formulas (2) and (3) so as to learn energy consumption of the entire network. Therefore, this paper will compute data load for each sensor node when sink is located at arbitrary (_x0 ,_y0 ). To the best of our knowledge, this paper gives derivation of data load in the network. It is also the basis for sink strategy in this paper.

Theorem 1.

Suppose the center of network be O(0,0) , the sink moved to A(_x0 ,_y0 ) , an optional sensor node B at (_xb ,_yb ), and the intersection point of AB extension with the network border is (_xc ,_yc ) , then the data load for B node is as follows: [figure omitted; refer to PDF]

Proof.

This paper applies the shortest path routing protocol to transmit data to sink through multihop. For an arbitrarily node B (_xb ,_yb ), see Figure 2; C represents intersection point of AB extension with the network border, and the data load for B is the amount of data whose distance from B is integer multiple of r on line BC . First, we calculate the coordinates of C(_xc ,_yc ) .

Equation of line AB : [figure omitted; refer to PDF] Equation of the circle: [figure omitted; refer to PDF] Formula (5) can be simplified as [figure omitted; refer to PDF]

Let _g1 =(_yb -_y0 )/(_xb -_x0 ),_g2 =-(_yb -_y0 )/(_xb -_x0 )_x0 +_y0 =_y0 -_g1x0

y = _{g 1} x + _{g 2} ; we can work out (_xc ,_yc ) by substituting it in formula (6): [figure omitted; refer to PDF]

Solving the coordinates of C can be divided into several situations as follows.

First . When x(i)...0;_x0

coordinates of C are as follows: [figure omitted; refer to PDF] if _xb <_x0 then [figure omitted; refer to PDF] if _xb >_x0 then [figure omitted; refer to PDF]

Second . When _xb =_x0

: if _yb =_y0 then this is the sink itself; no data needs to be sent;

: if _yb ...0;_y0 then _xc =_x0 ^xc2 +^yc2 =^R2 ;

: if _yb >_y0 then _yc =^R2 -^xc2 ;

: if _yb <_y0 then _yc =-^R2 -^xc2 .

According to coordinate of C , the length of line AC is [figure omitted; refer to PDF] The length of line AB is [figure omitted; refer to PDF]

Let _R1 =|AC|, α=[left floor]_R1 /r[right floor], _R1 =αr+b|"b...4;r : [figure omitted; refer to PDF] Data load of B is calculated as follows. Its distance from sink is D=|AB¯|=ir+c|"i∈{0...a}, x∈{0...b} .

Then check sector area [aleph] with angle of dθ and width of dx (see Figure 2). The dimensions of this area are approximately _[aleph]s =D dθ dx . The number of nodes in this ring is ρD dθ dx . If it is located in the {ir...ir+b}|"i∈{0...a}th ring, that is to say, the location is D=ir+c|" i∈{0...a}, c∈{0...b} , then data load of [aleph] is as follows.

It is responsible of forwarding all the remote data in sector area whose width is dx and is integer multiple of r away from [aleph] . The dimension of these areas can be computed as [figure omitted; refer to PDF]

This is the dimension of area [aleph] which is responsible of forwarding data. Then data load of [aleph] is [figure omitted; refer to PDF]

Data sent is [figure omitted; refer to PDF] It can be assumed that the data load is uniformly shared by each node in a very small region. Then data load of each node is [figure omitted; refer to PDF] Data sent is {dθ dx(ac+((1+a)ar/2))+dθ(ir+c)dx}ρ/dθ(ir+c)dx}ρ=1+((a-i)c+((i+1+a)(a-i)r/2))/(ir+c) .

If D=ir+c|"i∈{0...a}, c∈{b...r} is located in the {ir+b,ir+r}th ring data load of [aleph] can be computed as follows

It is responsible of forwarding all the remote data in sector area whose width is dx and is integer multiple of r away from [aleph] . The dimension of these areas can be computed as [figure omitted; refer to PDF] Then data received by [aleph] is [figure omitted; refer to PDF] Data sent is [figure omitted; refer to PDF]

It can be assumed that the data load is uniformly shared by each node in a very small region. Then received data of each node is [figure omitted; refer to PDF] Data sent is [figure omitted; refer to PDF]

Figure 2: Network computing model.

[figure omitted; refer to PDF]

Based on Theorem 1, Figure 3 shows the energy consumption map when sink is at different locations. As can be seen from the chart, energy consumption of the network is different when sink is in different locations; nodes near sink do not necessarily suffer higher energy cost. For example, when sink is located near the circumference, power consumption in network-centric side of sink is much higher than the other side near the edge of the network. In order to show more clearly the data load for sink in different orientations and positions, Figure 4 selects three straight lines from the map and Figure 8 shows the statistical chart of the data load on these three lines.

Data load of network.

(a) R = 500 , r=85 , sink(100,360)

[figure omitted; refer to PDF]

(b) R = 500 , r=85 , sink(-100,-360)

[figure omitted; refer to PDF]

(c) R = 500 , r=85 , sink(0,0)

[figure omitted; refer to PDF]

Figure 4: Selected A^{A[variant prime]} , B^{B[variant prime]} , and C^{C[variant prime]} positions.

[figure omitted; refer to PDF]

As can be seen from Theorem 1, data load of node is directly proportional to distance (BC length) from this node to circumference. The longer BC is, the more data node B has to bear. It can be seen from Figure 5 that SA [variant prime] line is the longest, and therefore SA [variant prime] line has to undertake the most amount of data, but data load of SA line on the other side is the smallest, although SA is the closest to sink. The situation of BB [variant prime] and CC [variant prime] lines is also not the same. This indicates generally the idea that nodes near sink suffer higher volume of data which is wrong. Besides, energy consumption will change with sink location and has close relations to the transmission range. Figure 6 shows data load of CC [variant prime] in Figure 4 under different communication range r . The general rule is that the bigger r is, the smaller the amount of data the node has to bear. The extreme case is when r=R every node sends data directly to sink. Each node at this time only has to bear one unit of data, which is the least.

Figure 5: Data load in different distances from sink in different directions.

[figure omitted; refer to PDF]

Figure 6: Data load under different communication ranges.

[figure omitted; refer to PDF]

Corollary 2.

Note the transmission range r with ^fri (x) ; sink has moved to A(_x0 ,_y0 ), an arbitrary node B(_xb ,_yb ); then the energy consumption of node B is [figure omitted; refer to PDF]

Proof.

According to Theorem 1, the amount of received data of nodes D=ir+x away from the sink is D_r and the amount of sent data is _Dt =_Dr +1 . Substituting them into energy formulas (1) and (2) will lead to Corollary 2.

Based on Corollary 2, Figure 7 shows the energy consumption under different sink locations and different r . As can be seen from the figure, the energy consumption of mobile sink is very complex. So it requires careful planning for moving sink.

Energy consumption of network (R=500 ).

(a) r = 80 , sink(350,0)

[figure omitted; refer to PDF]

(b) r = 150 , sink(0,0)

[figure omitted; refer to PDF]

(c) 150, sink(350,350)

[figure omitted; refer to PDF]

(d) r = 150 , sink(-350,-350)

[figure omitted; refer to PDF]

Figure 8: Energy consumption of nodes different distances from the sink in different directions.

[figure omitted; refer to PDF]

In order to examine the energy consumption of the network in detail, Figure 8 shows energy consumption map of the three lines selected from Figure 4. Figure 9 shows energy consumption of nodes located at different distance from the sink under various transmission ranges computed through Corollary 2. Different from data load, when node is located at the first r distance ring from sink, the transmission range is actually the distance to sink, so it is less than r . When distance from node to sink is larger than r , transmission range is all the same as r . Therefore, the energy consumption does not decline as the distance grows. Its law is that in the first ring where r is small, node close to sink has to undertake much higher data load; although the communication range is smaller than r , energy consumption rate is still very high. With the increase of r , data load declines very fast (see Figure 6), and thus energy consumption of nodes nearest from sink also drops very quickly. Although data load in the edge of first ring is smaller than that within the first ring, the transmission range is larger and hence energy consumption increases. Consequently, there is concave within r from sink in the power consumption chart (see Figure 9 energy consumption chart r = 125). From the second ring, the communication range is all r , but data load is smaller as they are farther from sink, energy consumptions also a decreasing function of distance from sink (see Figure 9). This paper reveals details of network energy consumption for the first time.

Figure 9: Energy consumption under different communication ranges.

[figure omitted; refer to PDF]

4.2. The Factor That Affects the Network Lifetime

Data collection strategy for mobile sink is as follows: sink moves to a new location to carry out k rounds of data collection and then moves to a new anchor. It goes on like this model until the death of the network. Suppose the total time sink can pause during the survival of the entire network which is Γ . Then goal for sink mobility is to find suitable anchors to achieve the longest life span of the network. And the essence is to maximize the number of rounds of data collection, that is, Max...(k×Γ) . As we define the lifetime as an interval till the death of the first node. Therefore, in order to achieve the longest life expectancy, it is necessary to minimize the largest energy consumption among all the nodes.

4.2.1. The Impact of the Number of Anchors

After migrating to the purpose location, sink will conduct data collection. The purpose location is termed as the anchor. The number of locations that sink can pause is termed as anchor number. In fact, the case of static sink can be summed up as the situation where there is only one anchor. From above we know that the center is the best sink location now. In addition, we are able to get the largest network lifetime (equal to static sink). However, when the number of anchor numbers increases to be more than one, the analysis of network life expectancy has become more complex. We assume that sink can move across the whole network, and the anchor number is infinite in theory. But the actual anchor number is limited as follows.

(1) Based on the principle of symmetry of a circular network with Proposition 2 (claim 2) in Luo and Hubaux's paper [17] have proven that the track of mobile sink is a ring. That is, trajectory of sink is limited to a circular track within the circle.

(2) Because of the limited energy resource of sensor node, the life span of the network is limited as n rounds. The sink conducts at least one round of data collection at each anchor; then anchor number is restricted to the n points on the circular track. Also, based on the principle of symmetry, these n anchor points should be uniformly distributed on the circular trajectory to achieve optimal network performance.

(3) The actual physical characteristics of the network, such as sink mobility, network topography, and geography, can limit the anchor sink's stay.

When the sink is located on a track (the track is a ring whose center is at origin; when the radius of ring is _Rm , it is termed as trajectory or orbit _Rm ) and the anchor location is determined, the algorithm below can compute the energy consumption for each network grid.

Based on Theorem 1, Figure 10(a) shows energy situation of five rounds of data collection for each anchor, and then move to the next location; there is a total of 50 anchors and 250 rounds of data collection. And in Figure 10(b) there is a total of 250 anchors and 250 rounds of data collection. It can be seen that under different anchor numbers, even if the two situations conduct the same rounds of data collection (the same network lifetime), the largest energy consumption in network whose anchor number is bigger is less than half of that in the former network (less anchor number). It indicates that anchor numbers have a greater impact on the network life expectancy. If we define quotient obtained by dividing the maximum energy consumption among all the nodes by the number of rounds of data collection as the network energy efficiency, then the energy efficiency of the network is higher, the higher life expectancy will be under the same initial energy and vice versa.

Energy consumption map under different anchor number (R=2000 , _Rm =2000 m , and r=85 ).

(a) Anchors = 50, maximum energy consumption E = 4.05e + 006

[figure omitted; refer to PDF]

(b) Anchors = 250, maximum energy consumption E = 1.53e + 006

[figure omitted; refer to PDF]

We also find that network energy efficiency increases with the growth of the anchor. But the efficiency will stay stable after anchor increases to a certain threshold.

The anchor number is mainly affected by the initial energy of node. If the initial energy is small, the life span of the network n will be short. However the anchor number cannot exceed n , so it will affect the network efficiency when n is small. Similarly, the larger the network is, the more energy for one round data collection will be, thus decrease the number of anchor.

Anchor number will not affect the energy efficiency of the network after it rises over certain degree, and the degree is related with the scale of the network. Let the radius of the sink track be _Rm ; study in this paper shows that the degree will be greater when _Rm increases and vice versa. The most special situation is that if _Rm = 0, then degree of sink is n=0 ; that is, the anchor number does not affect the network energy efficiency. From the above analysis we can see that anchor number of sink has great impact on network life expectancy. Therefore, previous studies which do not consider anchor number usually simplify the problem.

4.2.2. The Impact of Radius of Mobile Trajectory

Figure 11 shows the energy situation when _Rm is, respectively, 2000 m, 1200 m, 1000 m, and 800 m in network with R=2000 m and 50 sink anchors. Largest energy in _Rm =2000 m is not the minimum; instead, _Rm =1200 m has the minimum energy consumption. The above description indicates that the optimal trajectory of mobile sink needs to be carefully optimized and there will be a better route for the longest network life.

Energy consumption for different values of _Rm (R=2000 , rounds =50 , anchors =50 , r=85 ).

(a) _{R m} = 2000 m, max E = 8.1e + 5

[figure omitted; refer to PDF]

(b) _{R m} = 1200 , max E = 7.06e + 5

[figure omitted; refer to PDF]

(c) _{R m} = 1000 m, max E = 7.2e + 5

[figure omitted; refer to PDF]

(d) _{R m} = 800 m, max E = 7.5e + 5

[figure omitted; refer to PDF]

4.2.3. The Impact of Communication Range

The communication range r has a great impact on the network lifetime. Figure 12 shows the energy situation of the line which is 620 m from sink to the circumference (similar to |^{SA[variant prime]} |=620 m in Figure 4). It can be seen that energy situation changes with different r . The rule is as follows: with the increase of r , energy consumption of nodes near sink decreases, and energy consumption of nodes far from sink grows. The right chart in Figure 12 shows energy consumption under different length of |^{SA[variant prime]} |=L . The rule is that the greater L is, the higher energy consumption will become. Accordingly, the largest lifetime of static sink network is as follows: when L=R , the value of r which can minimize the maximum energy consumption on |S^{A[variant prime]} | is the value that can achieve the largest network lifetime. The energy consumption should be energy cost after one round of data collection. The quotient obtained by dividing node initial energy by the largest energy consumption is the largest network lifetime with static sink.

Figure 12: The relationship between energy consumption and r .

[figure omitted; refer to PDF]

Communication range r also has a great impact on the lifetime of mobile sink network. We can prove this point through experiment. Below is in the network with R=2000 , sink moving along the circumference, and sink pausing anchor should be only 50. Energy consumption in the trajectory is low; energy consumption on the trajectory is high. Therefore, when r increases, energy consumption in the trajectory will increase, and energy consumption on the trajectory will reduce. Figures 13(a), 13(b), and 13(c), respectively, show different maximum energy consumption under different r . We can see that the difference between network largest energy is nearly doubled when setting different r values.

The largest energy consumption of mobile sink network under different r (R=2000 m, _Rm =2000 m, rounds = 50, anchors = 50).

(a) r = 65, max E = 1.0474e + 006

[figure omitted; refer to PDF]

(b) r = 105, max E = 6.562e + 005

[figure omitted; refer to PDF]

(c) r = 125, max E = 5.6132e + 005

[figure omitted; refer to PDF]

Below is in the network with R=2000 , sink moving along the circumference, and sink pausing anchor increasing to 300. We can set different r values to achieve the smallest largest energy consumption, that is, the maximum network lifetime. Figures 14(a), 14(b), and 14(c) show different maximum energy consumption under different r . We can see that network lifetime is also not the same.

The largest energy consumption of mobile sink network under different r (R=2000 m, _Rm =2000 m, rounds = 300, anchors = 300).

(a) r = 55, max E = 2.146e + 006

[figure omitted; refer to PDF]

(b) r = 85, max E = 1.8465e + 005

[figure omitted; refer to PDF]

(c) r = 105, max E = 2.3052e + 006

[figure omitted; refer to PDF]

Figure 15 shows the energy situation after 155 rounds of data collection under different based on Theorem 1. There is a best to obtain the smallest total energy consumption and the largest network lifetime.

Figure 15: Maximum energy consumption under different r .

[figure omitted; refer to PDF]

Also r is related with the network overall energy consumption. Figure 16 shows the total energy consumption under different r after one round of data collection. The relationship between network total energy consumption and r is a concave curve; the concave point minimizes total energy consumption, which is also the best r value. The best r is not affected by the location of sink. As can be seen from the chart the amount of energy is the least when r=85 m.

Figure 16: Overall energy consumption under different r .

[figure omitted; refer to PDF]

5. A Distributed Algorithm for Mobile Sink

5.1. Distributed Algorithm for Mobile Sink

In our theoretical calculation nodes are uniformly distributed, and the external environment is homogeneous. But in practice, the deployment of network is always not uniform, and the external environment is not necessarily homogeneous (affected by physical barriers such as restrictions on the terrain). We find in experiments that the deployment of nodes has a great impact on the network lifetime, such as Figures 17 and 18. 3000 nodes are deployed in network with radius of 500 m. In Figure 18 nodes are randomly deployed; in fact, the deployment is uneven. Sparse region will lead to particularly high energy consumption in individual node; these nodes are located at (-104, -387) (76, -20) (-30,279). The energy consumption map is shown in Figure 19. Figure 20 is an energy consumption diagram of strictly uniform deployment. From observation of experimental results, the trend shown in Figure 19 is in line with the theoretical results. However, it is not as optimal as the results of Figure 20. It can be seen that offline methods cannot adjust sink location according to real world situation. Online distributed algorithm adaptability optimizes the choice of the sink anchors according to the actual energy consumption of the network, so its efficiency is relatively high and adaptable. Therefore, based on the previous theoretical analysis, we propose distributed mobile sink algorithm to avoid the energy hole.

Figure 17: Randomly deployed network.

[figure omitted; refer to PDF]

Figure 18: Uniformly deployed network.

[figure omitted; refer to PDF]

Figure 19: Energy consumption of randomly deployed network.

[figure omitted; refer to PDF]

Figure 20: Energy consumption of uniformly deployed network.

[figure omitted; refer to PDF]

The idea of Algorithm 1 is first to mesh network, then move sink to a grid(_X0 ,_Y0 ) , calculate the total energy of all the nodes by adding the actual energy consumed and the precalculated theoretical result, and then choose the largest energy EE as the compare energy for sink at (_X0 ,_Y0 ) and repeatedly we switch sink to next grid and calculate its compare energy . From all the compare energies , we choose the minimum one and set the correspondent sink coordinate as the optimal next pause anchor.

Algorithm 1: Find best location(e(1:n) ).

//To find the optimal sink anchor

(1) Maxenergy = 0;

(2) min_global_energy = ∞; //current value that minimize the maximum energy consumption

(3) For _x0 =-R:R

(5) For _y0 =^R2 -^x02

//sink can pause at any point of the network

(6) Maxenergy = 0;

//set the initial maximum energy consumption as 0

(7) for i=1:n //number of nodes

(8) for each r do

(9) computer energy E(i) consumption use Corollary 2

//compute energy cost of i node when sink is at (_x0 ,_y0 )

(10) Ea(i)=e(i)+E(i)

// e(i) represent the actual energy consumption of node i

(11) If Maxenergy < Ea(i) //when the energy

// consumption of i node is larger than current maximum

(12) Maxenergy = Ea(i) //compare energy of

//sink(_x0 ,_y0 ) is the energy consumption of node i

(13) Endif

(14) End for

(15) End for;

(16) If min_global_energy > Maxenergy // Maxenergy

//represent the maximum energy consumption of sink(_x0 ,_y0 )

(17) min_global_energy = Maxenergy

//minimize the comprehensive energy

(18) _xbest =_x0 ; _ybest =_y0 ;

//next sink anchor to minimize the comprehensive energy

(19) Endif

(20) End for

(21) End for

(22) Return(_xbest ,_ybest );

//return the optimal next sink anchor

The complexity of Algorithm 1 is m*n*n1*|r| ; m*n represents the number of grid, n1 represents the number of nodes, and |r| represents the transmission level of nodes.

5.2. Analysis of Mobile Strategy

Algorithm 1 only considers maximizing the life span of the network; sink pausing path is shown in Figure 21(a). However, it fails to discuss the mobility of sink. In fact, it may not be feasible to purely act according to Algorithm 1 in real application. Because the speed of the mobile sink should be slow, sink cannot move around the network without limitations in speed as described in Algorithm 1. In addition, sink mobility will bring extra recourse dissipation and cost; thus the shorter sink moves the better. For these reasons, we recognize that Algorithm 1 can be improved according to the fact that if the total pause of anchors for sink is N , then the network life is irrelevant with the sequence of pausing. Therefore, we can precalculate k -anchors in Algorithm 1, rather than one single anchor. As long as there is at least one of them located within the scope of current sink migration capability, then ideal moving path of sink is to form a ring around the network. Since the algorithm for calculating k -anchors is similar with Algorithm 1, due to space limitations, we omitted it here.

Path for mobile sink.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

6. Performance Analysis and Experimental Results Comparison

This paper applies OMNET++ to carry out experiments; OMNET++ is an open network simulation platform which is open source, component-based and modular for large network and has been widely recognized by the academic community [10]. Experimental parameters are shown in Table 1 from the literature [14], if there is no special note.

6.1. Mobile Sink Network Performance Analysis and Experimental Comparison

6.1.1. Impact of the Number of Anchor

Figures 22 and 23 show, respectively, the theoretical calculations and experimental results of energy consumption under different numbers of anchors. The charts show that theoretical results match the experimental outcome. Figures 24 and 25 compare the maximum energy consumption under different numbers of anchors. The maximum energy consumption is different. We can obtain the energy per round by dividing the largest energy consumption by the number of rounds. It is clear that if the energy per round is small, then the efficiency of network is high. Figures 26 and 27, respectively, show the energy per round . From the chart we can find that the more the anchors are, the better the network efficiency will be. However, after the number of anchor exceeds a certain degree, the network efficiency is stable.

Energy consumption under different numbers of anchor (theoretical value).

(a) R = 500 , _Rm =500 r=85 , anchors = 40, max energy = 62903

[figure omitted; refer to PDF]

(b) Anchors = 60, maximum energy = 94343

[figure omitted; refer to PDF]

(c) Anchors = 80 maximum energy = 125800

[figure omitted; refer to PDF]

Energy consumption under different numbers of anchor (experimental value).

(a) R = 500 , _Rm =500 r=85 , anchors = 40, max energy = 84277

[figure omitted; refer to PDF]

(b) Anchors = 60, maximum energy = 102729

[figure omitted; refer to PDF]

(c) Anchors = 80 maximum energy = 129168

[figure omitted; refer to PDF]

Figure 24: Maximum energy consumption under different numbers of anchor (theoretical value).

[figure omitted; refer to PDF]

Figure 25: Maximum energy consumption under different numbers of anchor (experimental value).

[figure omitted; refer to PDF]

Figure 26: Energy per round under different numbers of anchor (theoretical value).

[figure omitted; refer to PDF]

Figure 27: Energy per round under different numbers of anchor (experimental value).

[figure omitted; refer to PDF]

6.1.2. Impact of Transmission Range

Figures 28 and 29 show the comparison of network energy dissipation between theoretical analysis and experimental under different transmission ranges and mobile trajectory. We can see a comprehensive impact of r and trajectory radius on the network energy consumption and the trend experimental outcomes is very close to the theoretical results.

Energy consumption under different transmission range (theoretical value, R=500 , rounds = 20, anchors = 20).

(a) _{R m} = 400 , r = 55, maximum energy = 64071

[figure omitted; refer to PDF]

(b) _{R m} = 350 r = 85 , maximum energy = 44214

[figure omitted; refer to PDF]

(c) _{R m} = 500 , r = 125, maximum energy = 61590

[figure omitted; refer to PDF]

Energy consumption under different transmission range (experimental value, R=500 , rounds = 20, anchors = 20).

(a) _{R m} = 400 , r = 55, maximum energy = 74322

[figure omitted; refer to PDF]

(b) _{R m} = 350 r = 85 , maximum energy = 521200

[figure omitted; refer to PDF]

(c) _{R m} = 500 , r = 125, maximum energy = 73201

[figure omitted; refer to PDF]

Figures 30 and 31 show the maximum energy consumption when sink is on different route. If sink is located in the same trajectory energy consumption can be different for various communication radiuses. If sink is located in distinct trajectory discrepancy between network energy consumption is great. Therefore, optimization of the mobile program requires comprehensive consideration of variety of factors.

Figure 30: Maximum energy consumption under different transmission range and _Rm (theoretical value).

[figure omitted; refer to PDF]

Figure 31: Maximum energy consumption under different transmission range and _Rm (experimental value).

[figure omitted; refer to PDF]

Figures 32 and 33 show the energy consumption of nodes on the diameter after 20 rounds of data capture under different r and _Rm . The tendency in experimental result is in line with the theory.

Figure 32: Energy consumption after combining r and _Rm (theoretical value).

[figure omitted; refer to PDF]

Figure 33: Energy consumption after combining r and _Rm (experimental value).

[figure omitted; refer to PDF]

6.2. Performance Analysis of the Distributed Algorithm

The experimental scene is as follows: network radius R=500 , the numbers of sensor node equal to 3000. Similar with the scene shown in Figure 18, sink collects data for 150 rounds. Based on previous experiments, we know that centralized algorithm in this paper is the same as LUO [17]. We only need to contrast the centralized algorithm, static sink, and distributed algorithm.

As theoretical analysis and comparison have been discussed previously, we only compare experimental results here. Figure 34 shows the energy consumption of these three algorithms after 150 data gathering.

Experimental results comparison of static sink, centralized algorithm, and distributed algorithm.

(a) Static sink, maximum energy = 4.20747e + 006

[figure omitted; refer to PDF]

(b) Centralized algorithm, maximum energy = 626987

[figure omitted; refer to PDF]

(c) Distributed algorithm, maximum energy = 621562

[figure omitted; refer to PDF]

From the experimental results in Figure 34, the energy consumption of static sink is more than the mobile sink approach by nearly an order. The maximum energy cost in distributed algorithm is the smallest. It shows that the proposed algorithm of distributed mobile sink can further improve network lifetime.

Figure 35 shows the comparison of maximum energy consumption between centralized algorithm and distributed algorithm in the process of data collection. Figure 36 shows the trajectory of sink computed by distributed algorithm. We can see that the actual optimized track of mobile network is not complete the same as calculated routine. Distributed algorithm has extended the footprint of sink to inside of the network, rather than only moving on the circle.

Figure 35: Maximum energy comparisons between centralized algorithm and distributed algorithm.

[figure omitted; refer to PDF]

Figure 36: Mobile sink positions in distributed algorithm.

[figure omitted; refer to PDF]

Distributed algorithm proposed in this paper is superior to all other algorithms as distributed algorithm can adaptively adjust the next location of sink based on actual energy consumption of the entire network. There are similar endeavors in previous studies. This paper can first calculate theoretical energy consumption of the entire network, effectively guiding the sink migration. In contrast with the algorithm which considers energy of the nodes only within one hop of current sink, the algorithm here takes into account the overall energy consumption. Our algorithm is also superior to those algorithms which take area near the sink certainly as hotspot and each time move sink from hotspot to the region with the highest residual energy. Because we can neither simply believe that nodes near sink spend the highest energy consumption, nor that moving sink to the region which remains the highest energy will minimize the maximum energy consumption.

6.3. Network Remaining Energy Comparison

Figure 37 shows the residual energy ratio between static sink and mobile sink after 150 rounds of data gathering in network of R=500 m . The remaining energy ratio of static network remains greater than 70 percent all through the run, while the remaining energy ratio of mobile sink strategy drops with the rounds of data collection and finally stays unchanged. Sink mobility has greatly enhanced the energy utilization rate (by 30%). Figure 38 shows the network remaining energy ratio under different transmission radius and it indicates remaining energy ratios are not the same as communication range changes (residual energy ratio = 1 - (total energy consumption of all the nodes)/(number of nodes × maximum energy consumption)).

Figure 37: Residual energy ratios under static sink and mobile sink.

[figure omitted; refer to PDF]

Figure 38: Residual energy ratios under different transmission radius.

[figure omitted; refer to PDF]

We also analyzed the impact of network parameters on the network performance. The node density, from previous study, has little impact on network performance. However, uniformity of the deployment has impact on the network life span. The more uniformly the nodes are deployed, the higher network life expectancy will be. In addition, other factors include the initial nodes energy and the network size. The greater the initial node energy is, the more round it can carry out data collection and vice versa. While increasing the network scale will decrease the network lifetime. As the number of rounds of data collection is equal to the minimum docking anchor of sink node, if the network lifetime is higher, docking anchors will become more and thus energy efficiency increases. Finally, we also experiment on the impact of parameters on the network used in Table 1. Generally, they influence the network performance, however, not the trend.

7. Conclusion and Future Works

The main contribution of this paper is as follows: (1) presents a method to accurately calculate energy expenditure of the network when sink is located anywhere; (2) proposes an online distributed algorithm combined with practical sensor networks to achieve better practical significance. In theory analysis and experiment section, we analyze the factors that affect network life in detail. The conclusion is of more general significance.

Although this paper can present a more precise calculation of the energy consumption of the network, the complexity of distributed mobile algorithm is still relatively large. There are several future research works; although there are many theoretical computing for regular network, most of the networks are irregular. Their optimization of mobile sink has more far-reaching applications. Therefore, the next step we plan to extend the energy consumption calculation to general irregular network. Secondly, this paper handles the situation of single mobile sink and multiple mobile sinks, because of its complexity, has so far failed to reach a satisfying method. Based on the conclusion and theoretical calculations in this paper, we will pursue preferable solution for network with multiple mobile sinks [24].

Acknowledgment

This work was supported by China Postdoctoral Science Foundation (2012M511756).

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] W. Wang, V. Srinivasan, K.-C. Chua, "Extending the lifetime of wireless sensor networks through mobile relays," IEEE/ACM Transactions on Networking , vol. 16, no. 5, pp. 1108-1120, 2008.

[2] I. Chatzigiannakis, A. Kinalis, S. Nikoletseas, "Efficient data propagation strategies in wireless sensor networks using a single mobile sink," Computer Communications , vol. 31, no. 2, pp. 896-914, 2008.

[3] A. Liu, X. Jin, G. Cui, Z. Chen, "Deployment guidelines for achieving maximal lifetime and avoiding energy holes in sensor network," Information Sciences , vol. 230, pp. 197-226, 2013.

[4] S. Olariu, I. Stojmenovic, "Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting," in Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM '06), Barcelona, Spain, April 2006.

[5] J. Li, P. Mohapatra, "Analytical modeling and mitigation techniques for the energy hole problem in sensor networks," Pervasive and Mobile Computing , vol. 3, no. 3, pp. 233-254, 2007.

[6] X. Tang, J. Xu, "Adaptive data collection strategies for lifetime-constrained wireless sensor networks," IEEE Transactions on Parallel and Distributed Systems , vol. 19, no. 6, pp. 721-734, 2008.

[7] X. Wu, G. Chen, S. K. Das, "Avoiding energy holes in wireless sensor networks with nonuniform node distribution," IEEE Transactions on Parallel and Distributed Systems , vol. 19, no. 5, pp. 710-720, 2008.

[8] M.-H. Chiang, G. T. Byrd, "Neighborhood-aware density control in wireless sensor networks," in Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing (SUTC '08), pp. 122-129, June 2008.

[9] J. Lian, K. Naik, G. B. Agnew, "Data capacity improvement of wireless sensor networks using non-uniform sensor distribution," International Journal of Distributed Sensor Networks , vol. 2, no. 2, pp. 121-145, 2006.

[10] A. Varga, "The OMNET++ discrete event simulation system," version 3.3, http://www.omnetpp.org

[11] A. Hossain, T. Radhika, S. Chakrabarti, P. K. Biswas, "An approach to increase the lifetime of a linear array of wireless sensor nodes," International Journal of Wireless Information Networks , vol. 15, no. 5, pp. 72-81, 2008.

[12] M. Cardei, J. Wu, M. Lu, "Improving network lifetime using sensors with adjustable sensing ranges," International Journal of Sensor Networks , vol. 1, no. 1, pp. 41-49, 2006.

[13] P. Chen, B. O'Dea, E. Callaway, "Energy efficient system design with optimum transmission range for wireless ad hoc networks," in Proceedings of the International Conference on Communications (ICC '02), vol. 2, pp. 945-952, May 2002.

[14] A. A. Somasundara, A. Kansal, D. D. Jea, D. Estrin, M. B. Srivastava, "Controllably mobile infrastructure for low energy embedded networks," IEEE Transactions on Mobile Computing , vol. 5, no. 8, pp. 958-972, 2006.

[15] Y. T. Hou, Y. Shi, H. D. Sherali, S. F. Midkiff, "On energy provisioning and relay node placement for wireless sensor networks," IEEE Transactions on Wireless Communications , vol. 4, no. 5, pp. 2579-2590, 2005.

[16] J. Luo, J. Panchard, M. Piorkowski, M. Grossglauser, J. P. Hubaux, "Mobiroute: routing towards a mobile sink for improving lifetime in sensor networks," in Proceedings of the IEEE International Conference on Distributed Computing in Sensor Networks (DCOSS '06), vol. 4026, pp. 480-497, 2006.

[17] J. Luo, J.-P. Hubaux, "Joint mobility and routing for lifetime elongation in wireless sensor networks," in Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '05), pp. 1735-1746, Miami, Fla, USA, March 2005.

[18] M. Ma, Y. Yang, "SenCar: an energy-efficient data gathering mechanism for large-scale multihop sensor networks," IEEE Transactions on Parallel and Distributed Systems , vol. 18, no. 10, pp. 1476-1488, 2007.

[19] Y. Bi, L. Sun, J. Ma, N. Li, I. A. Khan, C. Chen, "HUMS: an autonomous moving strategy for mobile sinks in data-gathering sensor networks," Eurasip Journal on Wireless Communications and Networking , vol. 2007, 2007.

[20] D. Vass, A. Vidács, "Positioning mobile base station to prolong wireless sensor network lifetime," in Proceedings of the 1st International Conference on Emerging Networking Experiments and Technologies (CoNEXT '05), pp. 300-301, Toulouse, France, October 2005.

[21] W. Liang, P. Schweitzer, Z. Xu, "Approximation algorithms for capacitated minimum forest problems in wireless sensor networks with a mobile sink," IEEE Transactions on Computers , vol. 62, no. 10, pp. 1932-1944, 2013.

[22] E. Ekici, Y. Gu, D. Bozdag, "Mobility-based communication in wireless sensor networks," IEEE Communications Magazine , vol. 44, no. 7, pp. 56-62, 2006.

[23] G. Shi, M. Liao, M. Ma, Y. Shu, "Exploiting sink movement for energy-efficient load-balancing in wireless sensor networks," in Proceedings of the 1st ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing (FOWANC '08), vol. 5, pp. 39-44, May 2008.

[24] J. Luo, J. P. Hubaux, "Joint sink mobility and routing to maximize the lifetime of wireless sensor networks: the case of constrained mobility," IEEE/ACM Transactions on Networking , vol. 18, no. 3, pp. 871-884, 2010.