Research about sensors
Obstacle-Avoiding Connectivity Restoration Based on Power Adjustment and Node’s Movement in Disjoint Mobile Sensor Networks
Chun-hui WU, Hong-sheng CHEN* ,Wen-hua DAI College of Computer Science and Technology, Hubei University of Science and Technology, Xianning 437005, China
* Corresponding author: Phn +86-18986639920, E-mail: chenhs1981@163.com
Abstract—Mobile sensor networks (MSNs) have many applications in recent years, especially in some harsh environment, such as coastal and border protection, search- and-rescue, battlefield reconnaissance and so on. MSNs may suffer from a large-scale damage which causes many nodes to fail and the network to get partitioned into isolate islands. So in order to avoid negative effects on the application, restoring network connectivity is crucial in such case. In this paper, we propose a novel method, OACRPANM, which avoid obstacle to restore the networks based on power adjustment and node’s movement. In OACRPANM mainly include three phases: firstly detecting the boundary nodes of every isolate island, then adjusting the power of boundary node to restore the connection, and finally moving mobile nodes that avoid obstacle to the appropriate location to restore the connectivity of the entire network. Extensive simulation experiments demonstrate that the proposed method can guarantee network connectivity and reduce the total distance in practical environment.
Index Terms—Mobile sensor networks, Connectivity restoration, Obstacle-Avoiding, Power adjustment, Node movement
I. INTRODUCTION Mobile sensor networks (MSNs) [1] have been widely
used in hash environment, such as coastal and border protection, search-and-rescue, battlefield reconnaissance, underwater monitor, target tracking and so on. Due to the limited onboard energy, sensor nodes are easily to failure in hash environment, which may lead the network splitted into disjoint island. In such cases, the messages can not be sent to the base station and the network is not connected.
Thus, it is very important to restore network connectivity when network partitioning occurs. Many researchers have focused on this connectivity restoration problems. The existing solutions mainly include deploying relay nodes or moving the mobile nodes to the appropriate location. These methods do not consider digging the nodes’ penitential to restore the network connection. For example, generally sensor node has a number of power levels, Mica2 nodes support 30 power levels and Telos nodes support 8 levels. Different power levels lead to different communicating distance. There fore, adjusting nodes’ power may make the separated nodes to communicate and then restore the network connection. In addition, most of the solutions that moving the mobile nodes to the appropriate location are not consider the obstacle in the moving path.
However, power adjustment is generally used in topology control. In this paper we incorporate power
adjustment and consider the obstacle-avoiding to restore network connectivity. Of course, with the limited nodes’ power, the full network connectivity may not be restored by simply adjusting nodes’ power. But by combining power adjustment with nodes’ movement, we may find better solution to restore the connectivity of the entire networks in the practical environment. Our major contributions are summarized as follows:
(1) We explore the power adjustment and make obstacle-avoiding to realize connectivity restoration, and propose a method that obstacle-avoiding connectivity restoration based on power adjustment and node’s movement in disjoint MSNs.
(2) We propose an algorithm (OACRPANM) to realize the above methods which manly including three phases: firstly detecting the boundary nodes of every isolate island, secondly adjusting the boundary node’s transmission power to restore the network connectivity. If adjusting power can’t restore the connectivity of the entire networks, the third phase that involves moving the mobile nodes that avoid obstacle to the appropriate location to restore the entire network is executed.
(3) Extensive simulation experiments demonstrate that the algorithm proposed in this paper can make the entire networks connected and significantly reduce the total distance in practical environment.
The rest of this paper is organized as follows. In Section II, we summarize related works. In Section III, the model of connectivity restoration is defined. In Section IV, the algorithm proposed in this paper is described. Section V presents the simulation results of the proposed algorithms. Finally, Section VI concludes the paper.
II. RELATED WORKS
A. Connectivity restoration Connectivity restoration has been studied widely in
sensor networks. The aim of connectivity restoration is to make the entire network connected timely with the least resources and the information can be transmitted to the base station. The research of connectivity restoration can be classified into two approaches: one is deploy new relay nodes and the other is moving some mobile nodes.
1) deploying new relay nodes Sookyoung and Mohamed [3] propose a novel three-step
algorithm called federating network segments via triangular steiner tree approximation (FeSTA) to restore structurally damaged WSNs. FeSTA not only engages fewer relay nodes than that of contemporary schemes but also enables load
2016 International Conference on Information System and Artificial Intelligence
978-1-5090-1585-6/16 $31.00 © 2016 IEEE
DOI 10.1109/ISAI.2016.71
115
2016 International Conference on Information System and Artificial Intelligence
978-1-5090-1585-6/16 $31.00 © 2016 IEEE
DOI 10.1109/ISAI.2016.71
115
2016 International Conference on Information System and Artificial Intelligence
978-1-5090-1585-6/16 $31.00 © 2016 IEEE
DOI 10.1109/ISAI.2016.71
115
2016 International Conference on Information System and Artificial Intelligence
978-1-5090-1585-6/16 $31.00 © 2016 IEEE
DOI 10.1109/ISAI.2016.71
115
balancing among the deployed RNs. Fatih et al. [5] present a robust relay node placement heuristic for structurally damaged WSNs. The proposed approach establishes a topology that resembles a spider web, for which the segments are situated at the perimeter. This topology not only exhibits stronger connectivity than a minimum spanning tree but also achieves better sensor coverage and enables balanced distribution of traffic load among the employed relays. Fatih et al. [8] also propose optimized relay placement to federate segments in WSNs, and they presented a distributed Cell-based Optimized Relay node Placement (CORP) algorithm and explain the beneficial aspects of the resulting topology with respect to connectivity, and traffic balance.
2) moving mobile nodes Sookyoung and Mohamed [4] promote an effective
strategy that optimizes relay node placement using minimum steiner tree for restoring the connectivity among the segment by populating the least number of relay nodes, moves relay nodes from each segment toward the center of the deployment area. As soon as those relays become in range of each other, the partitioned segments resume operation. In Literature [6], Abbasi focuses on movement- assisted connectivity restoration in WSANs, and presents a Distributed Actor Recovery Algorithm (DARA), which opts to efficiently restore the connectivity of the inter-actor network that has been affected by the failure of an actor. DARA realizes the connectivity restoration and minimizes the movement overhead imposed on the involved actors. Kemal [7] presents a distributed Partition Detection and Recovery Algorithm (PADRA) to determine possible partitioning in advance and self-restore the connectivity in case of such failures with minimized node movement and message overhead. In literature [12], a mathematical model that minimizes the total travel distance for connecting a given number of partitions is proposed.
B. power adjustment In Literature [9] Seyed proposes a topology control
protocol and maintains the connectivity of the sensor network by adjusting the transition radius of the sensor nodes using the harmony search algorithm, which can decrease the energy consumption of the sensor network and prolong the network lifetime. Su et al. [10] use a simple mixed communication modes where the sensor nodes can communicate with cluster-heads in either single-hop or multi-hop mode to maintain the topology. They develop the analytical models to determine the optimal communication models. In literature [11], Hyunbum et al. propose a heuristic approach whose goal is to find the smallest node transmission range for K actors to cover a collection of sensor nodes within d-hop in WSANs. Moreover, the minimum transmission range r is guaranteed to be found using an integer-linear-programming formulation.
C. Obstacle-Avoiding In Literature [13], the author proposes obstacle resistant
deployment algorithms for WSNs, which involves the design of a node placement policy, a serpentine movement
policy, obstacle-handling rules, and boundary rules. By applying the proposed ORRD, the robot rapidly deploys a near-minimal number of sensor nodes to achieve full sensing coverage, even though there exist unpredicted obstacles with regular or irregular shapes. Literature [14] proposes presents a Steiner-point based algorithm to achieve the best practical performance in wire length and run time. Unlike many previous works, the Steiner-based framework is more focused on the usage of Steiner points instead of the handling of obstacles. Izzet Senturk and Kemal Akkaya[15] re-design an existing connectivity restoration approach in disjoint MSNs to fit these requirements and evaluate the performance issues when realistic terrains are assumed. Rather than following a direct path, movement trajectory is determined based on a path planning algorithm which considers the risk and elevation of terrain sections to be visited while avoiding obstacles and highly elevated terrain sections.
To the best of our knowledge, only Chunhui Wu and Hongsheng Chen[16] proposed an combining power adjustment and node's movement algorithm for connectivity restoration in sensor networks, but they don’t consider avoid obstacle, there is no previous study on connectivity restoration through combined power adjustment and node’s movement considering obstacle-avoiding.
III. MODEL AND PROBLEM
A. System Model The proposed OACRPANM approach can be applied to
networks that include mobile sensor nodes and obstacle. We assume a MSN spreads through an area of interest for border surveillance applications. Every node (sensor, mobile sensor) has a number of power levels, and they are assumed to have the ability to adjust the power level based on demand. The mobile sensor nodes are battery operated but are assumed to be less-energy constrained. They are assumed to have mobility capability which is only exploited whenever needed. In addition, they are assumed to know their locations through mechanisms like GPS. The MSN network is assumed to be partitioned due to a massive damage to the network, such as the following Fig 1. :
Figure 1 A partitioned MSNs
116116116116
We assume that the actors/mobile sensors can communicate to base station via range extension or other means as a one-time event when the damage occurs. Thus, the network topology information can be relayed to the base station which does the computations for the recovery process. We assumed a partition as an isolate island that is inter-connected.
B. Problem definition Our problem can be defined formally as follows: “Given
n isolate islands including static sensors and actors/mobile sensors. All of the nodes have a number of power levels and can be adjust timely, the actors and mobile sensors can avoid obstacle to move toward the appropriate location. The goal is to provide a distributed solution which will ensure that k isolate islands will be connected within a unique network by adjust the boundary node’s power or moving the nodes such that minimize the total moving
distance(i.e., � �
m
j
jd 1
) where dj is distance of the actor or
mobile sensor move.
IV. ALGORITHM In this section, we will describe the detail of our
proposed algorithm that obstacle-avoiding connectivity restoration based on power adjustment and node’s movement in disjoint mobile sensor networks (OACRPANM). It mainly has three phases as the following:
A. Phase –Detecingt the boundary nodes In this phase, firstly we use related boundary node
detecting algorithm to detect all the boundary nodes of every isolate island. Due to every node has GPS device, the location of every live node is known. So the nearest nodes between each pair of two isolate islands of the networks can be selected. For example, in Fig. 1, there are five isolate islands, AMN 1 and SN 4 are the nearest nodes between isolate Island 1 and 3.
B. PhaseII –Adjusting the boundary node’s transmission power to restore the network After determining the nearest nodes between the isolate
islands, the proposed algorithm will increase the transmission power of the nearest boundary nodes between each pair isolate islands from the current level to the highest level gradually. For example, between isolate island 1 and isolate island 3, transmission power of AMN1 and SN4 will be increased until the two islands are connected. When the two isolate islands connected, this process is end. If the transmission power reaches the highest level, the two isolate islands are still not connected, Phase III will be executed.
C. PhaseIII –Moving the actor or mobile nodes that avoid obstacle to the appropriate location to restore the entire network If phase II can’t restore the network, phaseIII will be
executed. In this phase, the main work is determining which
mobile nodes of each isolate island to move and where to move. Firstly ,we determine the target location of each mobile nodes. Then the approach named federating network segments via triangular steiner tree approximation (FeSTA) [3] is employed. FeSTA is a relay node (RN) placement heuristic to restore connectivity while minimizing the number of required RNs. Because the RN placement problem is an NP-Hard thus almost all solutions use heuristic. The aim is to reduce the RN count and establish the connectivity among the isolate islands. FeSTA is a best known heuristic in terms of its RN count and thus it is employed to reduce the number of target locations that will be correspond to RN locations.
FeSTA uses constructing triangular steiner tree method to connect the partitions of the networks, Firstly, FeSTA finds the best triangles and form islands of segments by establishing intra-triangle connectivity. Then, disjoint islands of segment are federated. Finally, the steinerized edges are optimized. The output of FeSTA is a set of target locations, T, and the set of interface nodes, I, in each partition.
After determine the target locations set T, We will move the correspond nodes to the target location. Now the problem is which nodes will move and where to move and how to avoid obstacle. Firstly, in order to maintain the connectivity of each isolate island, when we select the mobile node, it must not be the cut-vertex node. Secondly, in order to reduce the distance of node movement, we use the method of phase to select the nearest mobile nodes of each pair of isolate islands to move. Thirdly, when the path of the select node moving have obstacle, it will explore the left rule to pass the obstacle. If two nodes can’t connect two isolate islands, the above process is executed repeatedly until the two isolate islands connect. Repeatedly executing the second step, the entire network will be connected finally.
V. PERFORMANCE EVALUATION AND ANALYSIS In this section, we evaluate and analyze our proposed
heuristic algorithm, OACRPANM, and compared it with the optimal solution OBA to minimize the total travel distance for connecting a given number of partitions until now in literature [12] and the CPANMCR algorithm proposed in literature [16].
A. Experiment Setup and Performance Metrics In simulation, connected topologies are considered in a
1000m×1000m area. The transmission of every node has three range levels including 50m, 100m and 150m, and set 50m initial. The number of mobile nodes varies form 10 to 30, and isolate island varies from 2 to 5. To form the desired number of isolate islands, cut-vertex nodes (i.e., nodes whose absence partitions the network) in the topologies are randomly failed. Each test case has been tested with 40 different topologies for significance and the average is reported. We mainly consider the following performance metrics and parameters:
1) The total distance This is the total distance moved by all the mobiel nodes
as a result of restore the isolate islands. Our goal is to
117117117117
minimize this total distance, because the energy consumption is direct related with it.
2) The number of the mobile nodes and isolate islands The mobile nodes directly impact the efficiency of the
connectivity restoration, and the isolate island impact the number of moving nodes for recovery.
B. Results analysis We analyze the change of the total distance with the
change of the number of mobile nodes from 10 to 30 and the number of isolate islands from 2 to 5. The communication range of every node is 50m besides the nodes required to adjust transmission range involved in phase II.
Fig. 2 depicts the impact of the number of mobile nodes on the total distance. The total distance decreases when the mobile nodes increases, and the total distance of OACRPANM and CPANMCR is always lower than OBA, which indicate that our proposed OACRPANM is more efficient than OBA proposed in literature [12]. That also indicate that our algorithm save more energy cost with the increasing of mobile nodes. When the number of nodes is 10 and 15, the total distance is 410m and 190m. The advantage of our algorithm is very obvious, since OACRPANM and CPANMCR adjust the node’s transmission range to restore the networks. In some cases, it does not need moving mobile nodes. From Fig.2 we also can see the total distance of the OACRPANM algorithm proposed in this paper is always higher than CPANMCR, that’s because in this paper we consider the exist obstacle in the moving path. However, the OACRPANM is more efficient for practical environment.
Fig. 3 depicts the impact of the number of isolate islands on the total distance. As can be seen from the figure, the total distance decreases when the isolate islands increases. The total distance of OACRPANM and CPANMCR proposed in this paper is always lower than OBA, and the OACRPANM algorithm is always higher than CPANMCR , the reason is similar with the above discussion.
10 12 14 16 18 20 22 24 26 28 30 100
150
200
250
300
350
400
450
500
550
Number of Nodes
To ta
l D is
ta nc
e( m
et er
s)
OBA
OACRPANM
CPANMCR
Figure 2 Total travel distance with 3 isolate islands and varying number of nodes
2 2.5 3 3.5 4 4.5 5 150
160
170
180
190
200
210
220
Number of Nodes
To ta
l D is
ta nc
e( m
et er
s)
OBA
OACRPANM
CPANMCR
Figure 3 Total travel distance with 20 nodes and varying number of isolate islands
VI. CONCLUSION In this paper, we study connectivity restoration in MSNs,
and propose a connectivity restoration algorithm OACRPANM, which avoid obstacle to restore the networks based on power adjustment and node’s movement. Extensive simulation experiments demonstrate that OACRPANM is more efficient than OBA. CPANMCR can save more energy cost and more efficient for practical environment.
ACKNOWLEDGMENT This work was supported in part by the Dr. Start-up
Foundation of Hubei University of Science and Technology under Grant No. BK1522 and the National Natural Science Foundation of China under Grant No. 61373108 and the Natural Science Foundation of Hubei Province under Grant No. 2015CFC778.
REFERENCES [1] G. Wang, G. Cao, T. L. Porta, and W. Zhang, “Sensor relocation in
mobile sensor networks,” in Proceedings of the 24th International Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM05), Miami, FL, March 2005.
[2] I. F. Akyildiz and I. H. Kasimoglu, “Wireless sensor and actor networks: Research challenges,” in Elsevier Ad hoc Network Journal, vol. 2, pp. 351–367, 2004.
[3] F. Senel, M. Younis,Relay node placement in structurally damaged wireless sensor networks via triangular steiner tree approximation[J], Computer Communications ,vol. 34, pp. 1932–1941, 2011.
[4] S. Lee, M. Younis,Recovery from multiple simultaneous failures in wireless sensor networks using minimum Steiner tree[J], Parallel Distrib. Comput.vol. 70,pp. 525-536, 2010.
[5] F. Senel,M. Younis,and K. Akkaya,A Robust Relay Node Placement Heuristic for Structurally Damaged Wireless Sensor Networks[C],2009 IEEE 34th Conference on Local Computer Networks (LCN 2009) Zürich, Switzerland.
[6] A.A. Abbasi, M. Younis, and K. Akkaya, Movement-Assisted Connectivity Restoration in Wireless Sensor and Actor Net-works[J], IEEE Trans. Parallel and Distributed Systems, vol. 20, no. 9, pp. 1366-1379,2009.
118118118118
[7] K. Akkaya, F. Senel, A. Thimmapuram, and S. Uludag, Distributed Recovery from Network Partitioning in Movable Sensor/Actor Networks via Controlled Mobility[J], IEEE Transaction on computers, vol. 59, no. 2, pp. 1105-1120, 2010.
[8] F. Senel and M. Younis,Optimized Connectivity Restoration in a Partitioned Wireless Sensor Network[C],IEEE Globecom 2011 proceedings.
[9] S. Mahdi Jameii, A. Nikdel and K. Faez, An Intelligent Topology Control Protocol for Wireless Sensor Networks, in Proc. of ICCSE, 2012.
[10] H. Su and X. Zhang, Optimal Transmission Range for Cluster-Based Wireless Senso Networks With Mixed Communication Models, in Proc. of WoWMoM, 2006.
[11] H. Kim and Jorge A. Cobb, Optimal Transmission Range for Multi- hop Communication in Wireless snesor and actor Networks, in Proc. of IEEE LCN, 2011.
[12] M. Sir, I. Senturk, E. Sisikoglu, and K. Akkaya, “An optimization- based approach for connecting partitioned mobile sensor/actuator networks,” in Proceedings of 3rd International Workshop on Wireless Sensor, Actuator and Robot Networks (WiSARN), in conjunction with IEEE INFOCOM’11), April 2011, Shanghai, China.
[13] C.Y. Chang, C.T. Chang, Y. C. Chen, and H.R. Chang, Obstacle- Resistant Deployment Algorithms for Wireless Sensor Networks, IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, VOL. 58, NO. 6, pp. 2925-2941,2009.
[14] C. Liu, S.Yuan, S. kuo and J.Weng, Obstacle-Avoiding Rectilinear Steiner Tree Construction Based On Steiner Point Selection, ICCAD’09, November 2–5, 2009, San Jose, California, USA.
[15] Izzet Senturk and Kemal Akkaya, Energy and Terrain Aware Connectivity Restoration in Disjoint Mobile Sensor Networks, WLN 2012,Cleawater,Florida.
[16] Chunhui Wu and Hongsheng Chen, Combining power adjustment and node's movement for connectivity restoration in sensor networks, Applied Mechanics & Materials;2014, Issue 644-650, p2736.
119119119119