Quality of Service-Based Node Relocation Technique for

Research ArticleQuality of Service-Based Node Relocation Technique for MobileSensor Networks

Adnan Anwar Awan1 Muhammad Amir Khan 1 Aqdas Naveed Malik2

Syed Ayaz Ali Shah1 Aamir Shahzad1 Babar Nazir3 Iftikhar Ahmed Khan 3

Waqas Jadoon3 Naveed Shahzad1 and Rab Nawaz Jadoon 34

1Electrical and Computer Engineering Department COMSATS University Islamabad Abbottabad Campus 22060Islamabad Pakistan2Electronic Engineering Department ISRA University I-10 Markaz Islamabad Pakistan3Department of Computer Science COMSATS University Islamabad Abbottabad Campus 22060 Islamabad Pakistan4School of Information Science and Technology University of Science and Technology of China Hefei 230000 China

Correspondence should be addressed to Muhammad Amir Khan amirkhancomsatsgmailcom

Received 19 April 2019 Revised 7 July 2019 Accepted 16 July 2019 Published 22 August 2019

Guest Editor Dionisis Kandris

Copyright copy 2019 Adnan Anwar Awan et al is is an open access article distributed under the Creative Commons AttributionLicense which permits unrestricted use distribution and reproduction in any medium provided the original work isproperly cited

Wireless sensor networks (WSNs) deployed in harsh and unfavorable environments become inoperable because of the failure ofmultiple sensor nodesis results into the division ofWSNs into small disjoint networks and causes stoppage of the transmissionto the sink node Furthermore the internodal collaboration among sensor nodes also gets disturbed Internodal connectivity isessential for the usefulness of WSNs e arrangement of this connectivity could be setup at the time of network startup Ifmultiple sensor nodes fail the tasks assigned to those nodes cannot be performed hence the objective of such WSNs will becompromised Recently dierent techniques for repositioning of sensor nodes to recover the connectivity have been proposedAlthough capable to restore connectivity these techniques do not focus on the coverage loss e objective of this research is toprovide a solution for both coverage and connectivity via an integrated approach A novel technique to reposition neighbouringnodes for multinode failure is introduced In this technique neighbouring nodes of the failed nodes relocate themselves one byone and come back to their original location after some allocated time Hence it restores both prefailure connectivity andcoverage e simulations show our proposed technique outperforms other baseline techniques

1 Introduction

WSNs gained global attention in the present times ebuilding block of WSNs is a sensor node ese sensorsnodes can measure gather and sense the information fromthe external environment is information can be used fordecision making by the end users ere are various areas ofinterests for WSNs applications for example militarysurveillance and target tracking providing relief in a naturaldisaster monitoring biomedical health and exploration ofthe hazardous environment and seismic sensing [1 2]

e sensing nodes in WSNs have low power memoryand computational and radio capabilities On the contrary

these sensors must perform variety of thermal mechanicalchemical biological magnetic and optical tasks to measurethe environmental properties Furthermore these sensorsmust also communicate from hostileharsh environment viaattached radio to the base stationemajor power source ofthe sensor is the batterye secondary power supply may beequipped such as the solar panel to gather the power fromthe external environment An actuator can be attached tosensors depending on the type of sensor and application[3 4]

Typically WSNs have little infrastructure ey may becomposed of few sensors to thousands of sensor nodes forthe prescribed activities e researchers classied WSNs

HindawiWireless Communications and Mobile ComputingVolume 2019 Article ID 5043187 13 pageshttpsdoiorg10115520195043187

into two categories the structured and the unstructuredWSNs In the unstructured WSNs sensor nodes are denselydeployed ese sensors can be deployed in the field in an adhoc manner Once the network is deployed it remainsunattended to perform reporting and monitoring functionsIn unstructured WSNs maintenance of networks such asfailure detection and connectivity management is done in areactive manner because of random deployment of sensornodes Whereas in structured WSNs the preplanned ap-proach may be used for some or all sensors nodes e mainadvantage of structuredWSNs is the deployment of a limitednumber of sensor nodes with lower management cost andnetwork maintenance e drawback is that the deploymentof limited sensors in larger areas may result into an un-covered region [5]

WSNs have their own resource and design constraints Adesign constraint depends on the monitoring environmentand the type of application For example short-range ofcommunication limited power lower bandwidth andlimited storage and processing memory could result intodifferent designs e environment in which a WSN will bedeployed also plays a vital role in the formation of thenetwork size and network topology and the scheme of de-ployment Monitoring environment directly affects thenetwork size e indoor environment required a smallernumber of nodes for the formation of the network in alimited area while more nodes are required to form a net-work in the outdoor environment to cover larger area ead hoc deployment is better in a hostileout-of-range en-vironment where communication among sensors becomeslimited due to the obstacles in the environment [6]

Multiple sensors may fail simultaneously due to thehostileharsh environment In addition large-scale nodefailure involving multiple nodes may occur causing manydisjoint segments in a WSN Connectivity restoration is agreater challenge in this case as compared to the failure of asingle node problem In many cases simultaneous nodefailure is not contiguous yet it is expressively a much dif-ficult problem To the best of the authorsrsquo knowledge threetypes of approaches have been proposed in the recent re-search literature to reclaim multiple node failures

e first approach suggests that to restore connectivitythe topology of the network may be rearranged by reposi-tioning sensor nodes from the original positions of theWSNSuch techniques support self-healing of WSNs and are usedin a distributive manner e second approach recommendsthat multiple-relay sensor nodes should be deployed toreinstate the multiple dismember segments In the thirdapproach data is collected by the help of mobile muleswhich make trips to the critical areas and transfer that datafrom one partition to another in a WSN [7]

In context of the above sections the key contributions ofthis paper are elaborated as follows

(i) As the first contribution a technique to dynamicallyreposition the neighbouring nodes on multinodefailure is proposed to enhance network performance

(ii) e second contribution is energy efficiency of theproposed algorithm Here common neighbouring

nodes of the failure node must select one failurenode within their neighbourhood erefore thesenodes do not have to travel more than one node andthis saves energy

(iii) e third contribution is the better performance inQoS parameters like total distance travelled bynodes numbers of messages exchanged within allnodes average node relocation and reduction in thepercentage of field coverage as compared to otherbaseline techniques

e remaining paper is organised as follows Section 2highlights the relevant related work in a summarized mannerSection 3 discusses the details of the proposed algorithm forWSNs e energy model used is discussed in Section 4whereas the proposed algorithm validation and the simula-tion procedure are presented in Section 5 Section 6 concludesthe paper and proposes some possible future work

2 Related Work

e failure of the multinode problem has been addressedmany times in the literature in the recent past To handle themultinode failure problem the centralized approachesprovided better solutions ese approaches handle problemby developing a recovery schedule for multinode failure byrelocating nodes in WSNs Among these approaches in [7]the integer linear problem (ILP) is formulated for the re-covery problem In this work a nodersquos individual travellingdistance and coverage loss caused by multinode failure wereminimized by the optimization-based ILP that formed theconnected topology In this technique the position of thenode is assumed prior to the failure in WSNs In [8] atechnique grounded on the network flow transportationmodel is used where normally every single node should havethe capability to go to each destination of WSNs Here theproblem was solved by the polygon approximation modeland the formulation of mixed-integer approach is ap-proach is better from the approach provided in [9] in termsof total distance travelled However for more than 30 nodesthis technique does not measure accurately and results inerrors In [10] an alternative employment technique issuggested to reduce the number of node locations for im-proving scalability It is a practice to find the number ofpositions that promise connectivity if the relay sensors aredeployed at these locations As alternative relay sensors thecalculated locations are failed by the survival nodes in theWSN

In PADRA (partition detection and recovery algorithm)repositioned sensors are recognized by the CDS (connecteddominating set) of each partition and select the optimalnodes for recovery [11] A greedy heuristic method is used tominimize the total travelled distance of the sensors In thistechnique the nearest dominating pair of nodes are pickedand the dominate sensor is relocated to the target positione CDS of partitioned WSNs are updated until the con-nectivity is to be restored e result of this technique showsthat the heuristic method outperforms the solution andscales well as compared to [7 8] e distributed techniques

2 Wireless Communications and Mobile Computing

are proposed for the recovery of a single node and thesetechniques avoid the conflict which occurs during the re-covery e study by Imran et al [12] was an extendedversion of DCR (design of partitioning detection andconnectivity restoration) which handles multinode failures[9] is extended technique was known as RAM (recoveryalgorithm to handle multiple failures) and selected criticalsensors and designated backup for these nodes e keyparameter which enabled the RAM was the backup of theselection processes that handled the multiple simultaneousnode failures e idea was to improve the backup nodecriticality backup and primary deterioration at the sametime As the criticality improved it warrantied the desig-nating backups in the recursive fashion To avoid the racecondition mutex is used during the relocation of nodes toprevent the new failure is technique shows the toleranceof non-collocated multiple nodes and adjacent node failure

Similar approach as described above is used to toleratethe multiple sensor failures that occur at different locationssimultaneously [13] is technique uses the PADRA al-gorithm in multiple positions Two failure handlers are usedprimary and secondary In the primary handler there is noprespecified time for the recovery although the relocation ofthe nodes in a cascaded manner was donee two processesof recovery are required for the relocation of the same nodesto create the race condition at two different positions It isdifferent than a single node failure in which the neigh-bouring node of the failed node has a deterministic andreliable interpretation of the problem It is important tomake some assumptions like centre region knowledge routeknowledge and camera availability e major theme of thetechnique AUR (autonomous repair) is based on the re-locationrepositioning towards the preknown area centreand as per assumptions Vigorous nodes regrouped by AURand moved them towards the deployment centre area andtowards one another [14]e AUR design principle is basedon the connectivity modelling between neighbouring sensornodes AUR considers the localized repossession withsensors that interact with immediate neighbours e failednodes stretched the intrasegment topology If the restorationof connectivity is not done the block segment is movedtowards the centre deployment area e node density in thecentre point was increased by moving the segments towardsthe centre is ensures the reestablishment of the con-nectivity A distributed technique is used in the minimumSteiner tree (DORMS) for optimized placement of the relaynode which assumes that the network centre must be knownbeforehand [15] e difficulty is tolerated as the relay ap-pointment problem but relay nodes are selected among thesurvival nodes in theWSN partitions Hence to diminish thenumber of obligatory relays DORMS enhanced as Steinerminimum tree (SMT) K-LCA is employed by DROMSwhich reduced the number of the node for finding the to-pology [16]

Yet another technique is proposed to handle multiplenode failures by getting the knowledge of full paths of nodesto sink in [17] For determining the location of the damagednode prefailure route information is utilized e positionof the nodes and their path towards sink are then collected

after the establishment of the path e DARA (distributedactor recovery algorithm) calculates the probability toidentify cut vertices and select the neighbour node for thefailed node It relocates the neighbour node based on thecommunication link number [18] is technique is furtherenhanced by the proximity factor to the node failure andthen using PADRA for the optimization of the cascadedrelocation in intrapartition [19 20]

e technique in [21] is based on incomplete sensorfailure information e assumption of this work is to equipnodes with cameras to collect topology facts (normally thenumeral of end nodes) In this technique the function ofremuneration is established on a node degree where optionsto increase the node degree level are available In [22] theauthors proposed geometric skeleton-based reconnection(GSR) e approach split the network into various logicalsegments A group of nodes that have the maximum con-nectivity with other nodes is known as geometrical skeletonbackbone (GS backbone) e record of all the skeletalbackbone nodes is maintained by each segment In the caseof network segregation each segment attempts to join theGS backbone In this way connectivity can be restored In[23] HRSRT (hybrid recovery strategy established on ran-dom terrain) for restoration of connectivity is recommendedfor impaired WSNs e realistic terrain influence of area ofinterest (AOI) is considered in this algorithm e terrain isplanned by plotting the AOI and dividing it into a grid ofcells of equal size Each cell is characterized by the weight(cell) e weight of each path ω (Path) is also considered byadding the weight of each cell (cell) along path ω By (cell)and (Path) the thorough graph ldquoKnirdquo is built by taking theleast weight of paths between the segments RTPP (randomterrain-based path planning algorithm) is established byldquoKnirdquo for creating a tour T for connectivity restoration ofmobile data collectors (MDCs) Hence MDCs were re-sponsible for the restoration of connectivity e SACR(survivability-aware connectivity restoration) for segregatedWSNs by using mobile nodes is presented in [24] e levelsof load data of segregated segments for connection of theseparated segments of the segmented network were con-sidered by the SACR technique ese isolated segmentscould be found between different disconnected segmentse location of inaccessible segments is found by a group ofmoveable nodes to reinstate connectivity A relay partition iscreated for every isolated segment In [25] a robot controlstrategy for the provision of a connected path from the AOIto the base station is proposed by the authors e coreobjective of this algorithm is to find out smallest distancehaving a smaller number of hop counts for mobile robotswith unbroken network connectivity e proposed strategyencompasses two algorithms e first algorithm is to rec-ognize the nearest robot to the event area and assigns thatrobot to such location en this algorithm quests for thenearest nonallocated robot to ask it to forward itself to thecommunication range of any of the connected sectionhaving allotted robot e algorithm proceeds on till thenetwork is completely connected e second algorithmdiscovers out those locations which have minimum hopcount between the event area and the base station A method

Wireless Communications and Mobile Computing 3

for cut-vertex or critical-node determination is done in [26]is technique comprises two localized distributed algo-rithms to determine the states of nodes that they are eithercritical or noncritical Two-hop local subgraph and con-nected dominating set (CDS) information for the detectionof most of the critical and noncritical dominator nodes isused by the first algorithm e second proposed algorithmuses a limited distributed depth-first search algorithm inunrecognized parts of the network without going over thewhole network is algorithm determines the states of allnodes by comprehensive test bed experiments Simulationresults show that in the presence of a CDS this algorithmdiscovers all critical nodes using low energy consumptionTable 1 provides the summary of protocols discussed in therelated literature above

3 Details of the Proposed Algorithm

31 Problem Specification and Proposed Solution e loss ofmultiple sensor nodes because of the destruction batterydrainage or another malfunctioning not only disturbs theoverall coverage of the network but also limits the con-nectivity of WSNs e method of the proposed procedurefor the reinstatement of network connectivity and coverageis initiated in the same manner as C3R [27] Our proposedsolution takes the assumption that all sensor nodes areindependent from each other ie each sensor node takesdata from surroundings and uses other sensor nodes to sendthese data to the sink node e said algorithm in [27]suggests that the sensor nodes involved in recovery shall taketurns by moving to and fro from their original position tofailed node position is would result in prefailure cov-erage e problem arises in the said algorithm when theneighbouring nodes take part in the recovery process fail If aneighbouring node of a recovery node fails then a recoverynode must take care of both failed nodes ie the previousone and the latest one So the concerned node has to travelto and fro towards both failed nodes is may drain itsbattery very rapidly and make such recovery node as a failednode If a recovery node itself failed then there may be someother recovery neighbour nodes ey also must take care ofprevious and latest failed nodes and soon they will alsobecome failed nodes due to battery drainage Due to thisproblem coverage will be decreased To solve this probleman energy-efficient relocation of a neighbouring node for amultinode failure method has been proposed in this paperis method restores the prefailure connectivity as well ascoverage in the network As specified earlier the failure ofmultisensor nodes causing the network to be disjointed is themost challenging issue and of utmost importance Oursolution suggests that if the neighbouring node of recoverynode fails then the recovery node has to decide to take careof only one node previous or latest on the basis of itsdistance towards the failed nodes e concerned node willtake care of the failed node with a shorter distance eremight be a situation when there are two recovery nodeshaving the same distance to the latest failed nodes then thenode with higher ID will take care of the latest node and thelesser ID will stick to the previous node failure ere might

be a case when the recovery node itself fails due to somereason and it has neighbouring nodes which are part of theprevious node failed recovery process In such situationsuch nodes must decide whether they take care of theprevious node failure or latest failed recovery node based ontheir distance and coverage from both nodes So they willtake care of the node having a smaller distance with themis technique will save a lot of energy as the recovery nodesdo not need to travel to two nodes for taking care of them

32PrefailureOperations Aprefailure 1-hop neighboursrsquo listis maintained by a node in our proposed techniqueis list isgenerated as soon as nodes start off after deployment For anintroduction to its all neighbours a ldquoHELLOrdquo message isbroadcasted by each node in the network Besides this eachnode must know the location and neighbouring nodesrsquo IDse proposed algorithm uses normal GPS coordinates forlocations of neighbouring nodes is information ofneighbouring nodesrsquo locations is needed for use in case offailure of some sensor nodes HEARTBEATmessages are sentto all neighbours in a timely manner to confirm their live-liness erefore if a sensor node let us say A does notreceive its predetermined number of HEARTBEATmessagesfrom the neighbouring sensor node let us say F thenconsider F as the failed node After node failure detection asensor node will send a message about its movement towardsthe failed node to each of its neighbour nodes Each heartbeatcontains nodersquos ID and its location information Each nodesends HEARTBEAT messages after τ seconds On missingHEARTBEAT message each node waits for some allowednumber of heartbeats As there is a chance a HEARTBEATmessage can be missed due to packet loss due to some un-avoidable reasons After the completion of countdown timestill if a neighbourrsquos heartbeat is not received then thatneighbour is declared as failed nodeese thresholds of τ andcountdown must be chosen wisely that it must not be shortenough to declare an alive node failed which would triggerunnecessary recovery process and these thresholds must notbe long enough that the recovery process gets delayed Wehave not focused on optimization of these thresholds in thisresearch article as it is itself a research problem Our focus ison the recovery process

e recovery process is initiated by node A as soon as itcomes to know that the neighbouring node ie F has failedIt is notable that in the literature there are two approachesdiscussed when some node fails in the network e firstapproach determines if the failure of node F will divide thenetwork into disjoint partitions and the response will beestablished only if the failed node is a cut-vertex node istechnique avoids the overhead of communicating all thenodes in the network e drawback of this technique is thatit requires 2-hop information to find cut vertices in thenetwork hence messaging overhead is increased e sec-ond approach proposes the restoration process when con-nectivity and coverage are vanished irrespective of the failednode is a cut vertex or not e proposed technique uses thesimplest technique used in PCR (partitioning detection andconnectivity restoration) [9] In which each sensor node


determines itself as a critical or noncritical node by calcu-lating the distance between their neighbours by GPS co-ordinates by the famous haversine formula (details of theformula are given in Section 35 of this research article) Ifthe distance is less than the communication range (Rc) thenit declares itself as the noncritical node as its neighbours willstay connected on its failure Otherwise it declared it as thecritical node is technique will avoid all the recoveryprocesses triggered for leaf nodes and critical nodes will bedetermined in advance

33 Neighboursrsquo Node Management As mentioned earlierthat as momentarily as a node perceives that its neigh-bouring sensor node has failed it quickly starts the processof restoration of prefailure connectivity and coverage efirst thing that the sensor nodemust need to know is whetherthere are any other neighbouring sensor nodes of the failednode which can take part in the recovery process It ispossible if this node and each of the other neighbouringnodes ought to travel to the location of the failed node tillthey come in the communication range of each other eseneighbouring nodes of the failed node must travel thedistance of Rc2 towards the failed node If their commu-nication range is Rc then they can connect with each otherAs there is no solution provided in C3R for neighbouringnodes to detect the node failure and react to such situationwhen a recovery process is already going onerefore somesynchronisation of neighbouring nodes is needed for thissituation Besides this concern neighbouring nodes couldtravel to the position of the latest failed node to synchronisee travelling distance will be increased as there will be somecommon neighbouring nodes participating in the previousnode fail recovery process for which the recovery process isgoing on Such common nodes must travel to a previousnode failure location for its recovery process and to travel to

the latest node failure location is will result in an increasein overhead and their battery will be drained off very soonOur technique gives the solution that such common nodesmust decide to restrict them either with a previous failedrecovery node process or with the latest failure node processbased on the minimum distance and the maximum coveragearea from the failed nodes e calculations of distance andcoverage area and their relationship with each other aredescribed in detail in the next section

34 Distance between Nodes and Coverage Area e sensornode which reaches to the location of the failed node be-comes the coordinator of the recovery process If two nodesreach the failed location at the same time then the node withlesser ID will become a coordinator e role of the co-ordinator is to develop a recovery plan and distribute theturns of each node participating in the recovery process ecriteria for selecting the nodes taking part in the recoveryprocedure are constructed on the coverage overlap area ofthe nodes the distance between the failed node and theremaining energy they have e sensor nodes must reckonall these parametric values as they are criteria for selection inthe recovery process en these values are shared with thecoordinator of the recovery process e coverage overlap oftwo sensor nodes is the intersectional area of their com-munication range (Figure 1) e calculation of coverageoverlap becomes very simple when the disk coverage modelis taken in to account ere is an inverse proportionalrelationship between the distance between sensor nodes andthe coverage overlap When the distance between nodes issmaller then there will be a larger intersection between twocircles around the sensor nodes thereby increasing thecoverage overlap Two neighbour nodes will have coverageoverlapped if the distance (d) between them fulfils thecondition dle 2 times Rc For the distance ldquodrdquo between two

Table 1 Protocol summary

Reference Main objective Secondary goal Approachtype

State ofnetwork

Type ofmovement

[7] Connectivityrestoration Minimize the distance and coverage aware Centralized Global Controlled

[8] Connectivityrestoration

Minimize the maximum and totaldistance travelled Centralized Global Controlled

[10] Connectivity Minimize the maximum and total distance travelled Centralized Global Controlled[12] Connectivity Minimize the recovery scope and total distance Distributed 1-hop Cascaded[13] Connectivity Minimize the message cost and distance travelled Distributed 2-hop Cascaded[14] Connectivity Minimize the total distance travelled Distributed 1-hop Block

[15] Connectivity Minimize the relays populated number andcreate an efficient topology Distributed None Cascaded

[17] Connectivity Minimize the maximum and total distancetravelled Distributed 2-hop Cascaded

[20] Connectivity Minimize the total distance Distributed 2-hop Cascaded[21] Connectivity Minimize the total distance Distributed 2-hop Cascaded

[22] Connectivity Minimize the coverage loss and totaldistance travelled Distributed 1-hop Cascaded

[23] Connectivity Minimize the total distance travelled Centralized Global Cascaded[24] Connectivity Minimize the coverage loss Distributed 1-hop Controlled[25] Connectivity Minimize the coverage loss Distributed 1-hop Controlled[26] Connectivity Minimize the coverage loss Distributed 1-hop Controlled


nodes the following equations can be derived by using GPScoordinates of a sensor node 1 and its neighbour sensor node2 by the famous haversine formula

dlong long 2 minus long 1

dlati lati 2 minus lati 1

a (sin(dlati2))2

+ cos(lati1)lowast cos(lati2)

lowast(sin(dlong2))2

c 2lowast a tan 2(a

radic

1 minus a

radic)

d Rlowast c

(1)

where lati_1 is the latitude of node 1 lati_2 is the latitude ofnode 2 long_1 is the longitude of node 1 long_2 is thelongitude of node 2 dlati is the difference of lati_1 and lati_2dlong is the difference of long_1 and long_2 and R is theearthrsquos radius (mean radius 6371 km) note that anglesneed to be in radians

From Figure 1 the overlap of two nodes N1 and N2 canbe calculated if the area of the chord (pq) have angle β alsocalled as area (β) e distance between nodes N1 and N2 isfound at the start of nodes after deployment by GPS co-ordinates By using the law of cosines angle α can be foundas

angα 2 sinminus 1 d

2Rc (2)

e area (β) the area of the sector ldquopqrdquo depicted by blueshade in Figure 2 can be found by using the right-angledtriangle and using β2

area(β) βπ

R2c minus

d

2Rc times sin

β2

1113888 1113889 (3)

e overall coverage area can be found by multiplyingtwice the area of sector depicted by blue shade as the sectorarea in the blue shade is equal to the sector area in a lightgreen shade

Overlap 2 timesarea(β)

πR2c

1113888 1113889 (4)

35 Proposed Algorithm Implementation e implementa-tion of the proposed algorithm can be best understood by thescenario given in Figure 2 by considering the scenariodepicted in Figure 2(a) where node n7 has failed e stepsfor restoration of connectivity and coverage of the proposedalgorithm are explained below

(i) Initially the neighbouring nodes of failed node n7which are n2 n3 n4 n6 n8 and n10 will detectthat n7 has failed due to missing HEARTBEATmessage from node n7 and become recoverynodes

(ii) en these recovery nodes will calculate the dis-tance with n7 its coverage overlap and remainingenergy before they begin to move towards theposition of n7

(iii) Each recovery node sends a message of temporaryrelocation to their immediate neighbouring nodesand asks their neighbours to find alternating routeor buffer their data until such nodes return to theiroriginal position

(iv) All the recovery nodes move towards n7 to getconnected with each other e recovery nodewhich reaches the location first will become arecovery coordinator If two recovery nodes reachat the same time then the node with the lowest IDwill become the recovery coordinator

(v) e list of recovery nodes according to their pri-ority with regard to the parameters like the overlapof coverage distance travelled during relocationand amount of energy in remaining is maintainedby the coordinator node

(vi) After this recovery the node on the top of the listsuppose n2 will stay at the location of n7 and restof the neighbours will return to their respectivepositions and stay there until their turn

(vii) After some time the recovery node on the top ofthe list returns to its position and the second on thelist will resume the position of n7 On the returningto the original position a recovery node informs itsneighbour by broadcasting message to them andbegins to establish the transmission of the buffereddata again e same node will repeat a like presetprocess after that

(viii) Once the energy of a recovery coordinator nodereaches below the specified threshold level thecoordinator will transmit a request to other re-covery nodese recovery node presently situatedin the locality of n7 will accept the request erequest-receiving node will become a new recoverycoordinator travel to previous coordinator posi-tion and generate the new schedule

(ix) ere might be another situation such that if aneighbouring node of some recovery node failsduring the recovering process of some other nodeseg in Figure 3(a) recovery process of n7 is goingon and n10 fails en the neighbours of n10

90deg

Rc

RcRc

Rc

N1 N2

p

d

q

β

α

Figure 1 Calculation of overlapped coverage area of nodes N1 andN2


which are n2 n6 n8 n9 n10 n11 n12 n13 andn14 will have to take part in the recovery processHowever n2 n6 and n8 must decide whether theyremain to restrict with the n7 recovery process ortake part in the n10 recovery process

(x) For the decision purpose the one having lesserdistance amongst n6 n8 and n9 from n10 will take

part in the recovery process of n10 Besides thisthe node which is already at the place of theprevious failure node ie n2 in the examplecannot take part in the latest node failure recoveryprocess e selected node will take part in thelatest node failure and will detach itself from therecovery process of the previous node failure

n24n25

n26

n15 n16n17

n18

n13n12n14

n9

n11n10

n8n7

n6n1

n3n4

n5

n23n22

n21

n20

n2n19

(a)

n24n25

n26

n16

n18

n17

n14

n13n12

n9n10

n11

n8

n5n4

n23

n3

n3n4

n8n10

n6n2

n6n1

n2

n20

n19

n21n22

n15

(b)

Figure 2 (a) First node failure (b) Recovery process after the first node failed

n18

n5

n23

n11

n14

n8

n4

n22

n17

n26

n16

n2

n3

n21

n2

n20

n1n6

n9n10

n15

n12

n24n25

n19

n13

(a)

n24n25

n26

n17n16n15

n12n14

n18

n13

n13n12n9 n14

n11n9

n6

n8

n5n4

n23n22

n3

n21

n2

n20

n19

n1n6

n2

n11n8

(b)

Figure 3 (a) During the recovery process another node failure happened (b) Recovery process after the failure of the latest node


(xi) e recovery coordinator of the previous nodefailure will update the recovery list by excludingthe entry of a selected node which has detacheditself from such a recovery process

(xii) If the recovery coordinator of the previous nodefailure is self-selected as the recovery node forlatest node failure then it will inform other re-covery nodes taking part in the previous nodefailure recovery so they can nominate any node astheir new coordinator

(xiii) Figure 3(b) shows that n2 will remain at the failedlocation of n7 whereas n6 and n8 will compete forthe recovery node of n10 and the node with lesserdistance will win the competition

(xiv) If both n6 and n8 have same distance with failednode n10 then higher ID will become the recoverynode for latest node failure and lesser ID noderemains as the recovery node for the previous nodefailure (Algorithm 1)

4 Energy Model

An energy model which we have used in this paper ispresented in [28] e energy consumption of a node totransmit and receive a ldquoB-bit data packetrdquo over distance ldquodrdquois shown in equation (5) e energy expended per bit by thereceiver circuit is given by (6) Whereas the residual energycan be calculated by equation (7)

ETx(B d) Eelec + εfsd2( 1113857B dltd0

Eelec + εmpd41113872 1113873B dged0

⎧⎨

⎩ (5)

ERx(B) ERxminus elec B (6)

Ereng(n) Emax minus ETx(B d) minus ERx(B) (7)

Different terms used in this model are explained inTable 2

5 Simulations and Results

All the simulations were carried out using the platform ofOMNet++ for the performance appraisal of the proposedalgorithm A comparison is made between the proposedalgorithm with and increased robustness against recurrentfailure (RIR) of damaged WSN topologies in the event ofmultiple node failures [25] and autonomous repair (AuR)[26] protocols is section presents niceties of the simu-lation setup and the discussion of the results

51 Simulation Parameters e accomplishment of theproposed algorithm is authenticated through simultaneoussimulations is section discusses the simulation setupperformance metrics and results For the validation of theresults the OMNeT++ platform is used All the simulationparameters are given in Table 3

All the results are subjected to 90 confidence analysisinterval and stay within 10 of a simple mean

52 Results and Discussion For the analysis and perfor-mance comparison of the parameters such as the number ofmessages exchanged distance travelled by nodes number ofnodes relocated and reduction in the percentage of fieldcoverage and recovery time consumption of the proposedalgorithm RIR and AuR were employed

521 Distance Travelled e total distance that the nodestravelled while performing the recovery process is presentedin Figure 4 e sensing and communication ranges aretaken as equal in all these series of experiments How far thenode should travel depended on nearness of one node toanother node is vicinity was at most the Rc communi-cation range erefore an increase in Rc there was anincrease in how far a sensor node travelled is was easy incases of AuR and RIR as the distance travelled increasesrapidly Unlike AuR and RIR with the proposed techniquethe sensor node participation was limited in the recoveryprocess to the neighbours of the sensor node that failed Itdoes not use cascaded relocation that is initiated in AuR andRIR It is very significant to designate that when commu-nication range (Rc) is too high the proposed procedureshows the growth in connectivity of the WSN very well

522 Number of Packets Exchanged e number of packetsthat were exchanged ie received and delivered during therestoration of connectivity using each of the three methods ispresented in Figure 5 Every broadcast message was a singlemessage Using the proposed technique messaging over-head was negligible However using AuR provided themaximum number of the packets exchanged e reasonbehind this is that in the proposed technique onlyneighbour nodes of the failed node were involved in therestoration process On the contrary with AuR and RIR themessage exchange had to coordinate their achievement witha total number of nodes that were relocated However therewas an increase in network connectivity for large Rc is isbecause of the interaction which rarely takes place betweenother involved sensor nodes and recovery coordinators eproposed technique can be scaled up for the several roundsAlso it would offer coverage and connectivity reestablish-ment at the sensible price Comparative performance hasshown improvement in the proposed solution Hence byFigure 5 it is confirmed that a minute messaging overhead isadded by the proposed procedure

523 Number of Relocated Nodes Figure 6 shows the re-covery process of the total number of nodes relocated in thealgorithms used for the comparison purpose with theproposed algorithm For this purpose the total distancetravelled will increase with a greater number of travellingnodes From Figure 6 the result shows that the nodemovement of RIR is greater than AuR In any circumstancesin the proposed technique there are a smaller amount ofnode movements because the proposed algorithm restrictsthe time of the recovery process to the neighbour nodes ofthe failed node


Input distances of neighbouring nodes(1) IF (node A detects the neighbour node F had been failed)(2) Routing table updated (information about failed node will be deleted)(3) IF F leaf node(4) Do not move(5) Else(6) On-board energy level check(7) IF (energy is sufficient)(8) Calculate the area of the overlapped coverage(9) Broadcast ldquoTemporary Relocationrdquo MSG to neighbours(10) move to (F)(11) END IF(12) ELSE IF (the node A receives ldquoTemporary Relocationrdquo)(13) Search (new route)(14) IF new route available(15) Transmit data to a new path(16) IF (new route undiscovered)(17) Buffer the Data(18) END IF(19) ELSE IF node A receives (ldquoBack to original positionrdquo)(20) IF (data is buffered)(21) Send data using ldquoreallocated back noderdquo(22) END IF(23) END IF

Temporarily Relocation to (F)(24) Step towards F(25) IF (reached F)(26) Broadcast ldquoWill manage recoveryrdquo message(27) Coordinator 1(28) END IF(29) IF (received ldquoWill manage recoveryrdquo from node j)(30) IF (IDge j) Coordinator 0(31) Stop moving(32) Transmit relevant data to the coordinator(33) Receive recovery schedule(34) IF (first node not on schedule)(35) Relocate back to orign ()(36) END IF(37) IF Coordinator 1(38) From all concerned nodes collect significant information(39) Form ranked list and recovery schedule(40) Broadcast recovery schedule(41) IF (not the first node on schedule)(42) Relocate back to self ()(43) END IF(44) ELSE IF(45) Relocate to (F)(46) END IF

Another neighbour node failed during the recovery process(47) IF (node A detects the neighbour node J had been failed)(48) Routing table updated(49) On-board energy level check(50) IF (energy is sufficient)(51) Compare (distance F with distance J)distance F distance bw A and F distance J distance bw A and J(52) IF distance Flt distance J(53) Do not move to J(54) IF distance Fgt distance J(55) Broadcast ldquoGoing to save Jrdquo MSG to recovery nodes(56) move to (J)(57) Go to (step 5)replace F with J(58) IF receive (Going to save J)(59) Update list(60) END IF

ALGORITHM 1 Proposed algorithmrsquos pseudocode


524 Percentage Field Coverage Reduction e impact ofthe restoration process on coverage is illustrated in Figures 7and 8 It can be observed from the figures that the percentagereduction of the field coverage is considered by using thelevel of coverage before the failure and the level after thefailure e overall loss in coverage is limited reasonably byour proposed algorithm Furthermore for networks wherenodes are not dense and evenly distributed the overlappingcoverage is at the minimal level under the proposed algo-rithm and the field coverage is reduced equitably as com-pared to RIR A greater field coverage reduction wasobserved in RIR when the overlapping of the coverage of thenodes began to rise which are in cases where the nodes weredeployed in a dense manner e prefailure field coveragelevel was restored by applying the proposed algorithm is

restoration was done by the fact that the auxiliary nodes onlymove a little distance or do not move because of the growthin the coverage overlap Besides this there were numerousnodes available for the relocation process However net-works with sparse node positioning did not have adequatenodes that could be substituted by the failure node Fur-thermore a greater area was left unattended with the

Table 2 Meaning of different terms in the energy model

Term MeaningETx Energy consumption of node for transmissionERx Energy consumption to receive data by a nodeEreng Residual energyEelec Energy consumed per bit by the transmitter circuitryEmax e initial energy of sensor nodesERxminus elec Energy consumed per bit of a receiver

εfsEnergy required for a radio frequency (RF) amplifier

in free space

εmpEnergy required for a radio frequency (RF) amplifier

in multipathd0 reshold distance

0500

100015002000250030003500400045005000

Tota

l num

ber o

f pac

kets

exch

ange

d

125755025 100Communication range (m)

RIRAuROur approach

Figure 5 No of packets exchanged vs Rc in meters

No

of m

oved

nod

es

0

100

200

300

400

500

600

50 75 100 12525Communication range (m)

RIRAuROur approach

Figure 6 e total number of relocated nodes vs Rc in meters

No

of m

oved

nod

es

0

1

2

3

4

5

6

7


RIRAuROur approach

Figure 7 Percentage field reduction vs Rc in meters

Table 3 Simulation parameters

Simulation parameters ValuesSimulation area 900times 900m2

Number of nodes 25ndash150Data packet size 800 bitsEelec 50 nano-JoulebitEmax 20 Jεfs 10 pico-Joulebitm2

εmp 00013 pico-Joulebitm2

d0 75mRc 25ndash150mSimulation tool OMNeT++

RIRAuROur approach

0

05

1

15

2

25

Tota

l dist

ance

trav

elle

d (m

)

50 1257525 100Number of nodes

times104

Figure 4 Total distance travelled vs number of nodes


relocation of nodes resulting in creation of a gap in thecoverage of the network e percentage reduction ofthe field coverage for several communication and sensingranges is revealed in Figure 9 Fair coverage reduction wasperceived when Rc(communication range) dominated Rs(Sensing range) is was because longer distances neededto be travelled by the nodes between their home area and theposition of the node they were replacing Even so the re-duction was limited to 10 with the proposed algorithmeven if Rs is taken as six times theRc ie Rc 6Rs

525 Recovery Time Consumption Figure 10 shows thetime consumption of recovery process by the sensor nodeswhen the number of recovery nodes increases due to thefailure of other sensor nodes in WSNs erefore for cal-culating recovery time of our approach and other baselineapproaches τ is taken as 5 secs Whereas there are threeallowed number of missed heartbeats So overall a nodewaits for 25 seconds for its neighbour to respond It isobvious that with the increase in recovery nodes timeconsumption will be increased as recovery nodes must covermore distance But it is also a fact and it is clear fromFigure 10 that our proposed approach takes less recoverytime as compared to RIR and AuRemain reason is that asit is discussed earlier that our approach does not havecascade movements and the recovery process is only re-stricted to the neighbouring nodes en it is obvious thatthe proposed approach will take less time to recover becausenow recovery nodes do not cover large distances as in thecase of cascade movements Besides this distance is theprime criteria for the recovery nodes in case of multiple nodefailure ie recovery nodes restrict themselves to the re-covery process of the failure nodes having lesser distance tothemat is why the recovery time of our approach is lesserthan the other baseline approaches

526 Resultsrsquo Summary eOMNeT++ platform is used toevaluate the performance of the proposed protocol tocompare alongside the existing baseline algorithm It is

revealed from the results of simulations that the proposedalgorithm accomplished substantial energy-saving and im-proved the network lifetime It can easily be concluded fromresults that the proposed approach is operative in refiningparameters of quality of service like the number of ex-changed messages average number of nodes relocated andreduction of the percentage of field coverage reductionwhen compared with RTR and AuR techniques Table 3reviews the conclusions from these results (Table 4)

6 Conclusion

e maintenance of connectivity and coverage is very im-portant in mobile sensor networks Node failure may par-tition the network which causes the operations ofapplication to be malfunctioned e proposed proceduredeals with the connectivity-loss issue as well as the issue ofcoverage by not relocating the nodes in a permanentmanner e neighbouring nodes are responsible for thenode failure recovery e neighbouring nodes of the failed

Rc = 125Rc = 100Rc = 75

Rc = 50Rc = 25

No

of m

oved

nod

es

0

2

4

6

8

10

12

14

50 75 10025 125Communication range (no of nodes = 125)

Figure 9 Percentage reduction in field coverage for the proposedtechnique vs Rc for different communication ranges in meters

RIR (75 nodes)AuR (75 nodes)Our approach (75 nodes)


No

of m

oved

nod

es

0

2

4

6

8

10

12

14

50 75 100 12525Sensing range (m)

Figure 8 Percentage field reduction for the proposed technique vsRs in meters

Reco

very

tim

e (m

in)

102030405060708090

100

RIRAuROur approach

1007550 12525Number of nodes

Figure 10 Number of nodes vs their recovery time consumption


node organize between themselves to fix roles of each nodein the process of the recovery For the restoration of con-nectivity all the neighbouring nodes contribute in the re-covery process to transfer the nodes to the location of thefailed node to bring prefailure coverage in the location of thefailed node After expenditure an allocated expanse of timeat the place of the failed node each recovery node returns toits original location Stability in connectivity and coverageprovided by the proposed algorithm enhanced the lifetime ofthe network e proposed method is a hybrid form oflocalized and distributed algorithms Overall messagingoverhead is minor and for trivial networks the proposedalgorithm can be evaluated e endorsement effectivenessand validity of the proposed scheme are accomplished byextensive simulations

Data Availability

No data were used to support this study We have conductedthe simulations to evaluate the performance of the proposedprotocol However any query about the research conductedin this paper is highly appreciated and can be asked from theprincipal author (Adnan Anwar Awan) upon request

Conflicts of Interest

e authors declare that there are no conflicts of interestregarding the publication of this paper

Authorsrsquo Contributions

Adnan Anwar Awan Muhammad Amir Khan and AqdasNaveed Malik conceived and designed the experimentsAdnan Anwar Awan Muhammad Amir Khan and SyedAyaz Ali Shah performed the experiments MuhammadAmir Khan Aamir Shahzad and Naveed Shahzad analyzedthe data Adnan Anwar Awan Muhammad Amir Khan andAqdas Naveed Malik wrote the paper and Babar NazirIftikhar Ahmed Khan and Waqas Jadoon technicallyreviewed the paper Rab Nawaz Jadoon contributed intechnical revisions and final technical proofreading

Acknowledgments

e authors are thankful to Isra University Islamabad andCOMSATS University Islamabad for fully supporting byproviding all key resources during the implementation andall afterward phases of this project e authors would alsolike to personally thank Dr Muhammad Amir Khan and Dr

Aqdas Naveed Malik for their continuous encouragementand massive support both academically and socially duringthis project is project is partially funded by WirelessSensor Network Lab

References

[1] R N Jadoon W Zhou I A Khan M A Khan andW Jadoon ldquoEEHRT energy efficient technique for handlingredundant traffic in zone-based routing for wireless sensornetworksrdquo Wireless Communications and Mobile Computingvol 2019 Article ID 7502140 12 pages 2019

[2] R N Jadoon W Zhou W Jadoon and I A Khan ldquoRARZring-zone based routing protocol for wireless sensor net-worksrdquo Applied Sciences vol 8 no 7 p 1023 2018

[3] M A Khan H Hasbullah B Nazir and I A Khan ldquoAnenergy efficient simultaneous-node repositioning algorithmfor mobile sensor networksrdquo =e Scientific World Journalvol 2014 Article ID 785305 14 pages 2014

[4] A Khelil F K Shaikh A Ali N Suri and C Reinl ldquoDelay-tolerant monitoring of mobility-assisted WSNrdquo in DelayTolerant Networks Protocols and Applications p 189 Auer-bach Publications Boca Raton FL USA 2016

[5] Y K Joshi and M Younis ldquoRestoring connectivity in a re-source constrained WSNrdquo Journal of Network and ComputerApplications vol 66 pp 151ndash165 2016

[6] M Ilyas and I Mahgoub Smart Dust Sensor Network Ap-plications Architecture and Design CRC Press Boca RatonFL USA 2016

[7] A Alfadhly U Baroudi and M Younis ldquoOptimal noderepositioning for tolerating node failure in wireless sensor actornetworkrdquo in Proceedings of the 2010 25th Biennial Symposiumon Communications IEEE Kingston Canada May 2010

[8] M Y Sir I F Senturk E Sisikoglu and K Akkaya ldquoAnoptimization-based approach for connecting partitionedmobile sensoractuator networksrdquo in Proceedings of the IEEEConference on Computer Communications Workshops(INFOCOM WKSHPS) Shanghai China April 2011

[9] M Imran M Younis A M Said and H Hasbullah ldquoParti-tioning detection and connectivity restoration algorithm forwireless sensor and actor networksrdquo in Proceedings of the 2010IEEEIFIP 8th International Conference on Embedded andUbiquitous Computing (EUC) Hong Kong China December2010

[10] I F Senturk K Akkaya and S Fatih ldquoAn effective andscalable connectivity restoration heuristic for mobile sensoractor networksrdquo in Proceedings of the Global CommunicationsConference (GLOBECOM) IEEE Anaheim CA USA De-cember 2012

[11] X Bai S Kuma D Xua Z Yun and T H La ldquoDeployingwireless sensors to achieve both coverage and connectivityrdquo inProceedings of the 7th ACM International Symposium onMobile Ad Hoc Networking and Computing ACM FlorenceItaly March 2006

[12] M Imran M Younis A Md Said and H Hasbullah ldquoLo-calized motion-based connectivity restoration algorithms forwireless sensor and actor networksrdquo Journal of Network andComputer Applications vol 35 no 2 pp 844ndash856 2012

[13] K Akkaya F Senel A immapuram and S UludagldquoDistributed recovery from network partitioning in movablesensoractor networks via controlled mobilityrdquo IEEE Trans-actions on Computers vol 59 no 2 pp 258ndash271 2010

[14] M Younis I F Senturk K Akkaya S Lee and F SenelldquoTopology management techniques for tolerating node

Table 4 Resultsrsquo summary

Comparisonof protocolsfor 125nodes

Averagedistancetravelled(m)

No ofmessagesexchanged(average)

No ofnodes

relocated(average)

agereduction infield coverage(average)

Proposedtechnique 2600 400 50 4

RIR 14000 2000 200 13AuR 19000 4500 700 19


failures in wireless sensor networks a surveyrdquo ComputerNetworks vol 58 pp 254ndash283 2014

[15] S Lee and M Younis ldquoRecovery from multiple simultaneousfailures in wireless sensor networks using minimum Steinertreerdquo Journal of Parallel and Distributed Computing vol 70no 5 pp 525ndash536 2010

[16] G Robins and A Zelikovsky ldquoTighter bounds for graphSteiner tree approximationrdquo SIAM Journal on DiscreteMathematics vol 19 no 1 pp 122ndash134 2005

[17] S Vemulapalli and K Akkaya ldquoMobility-based self routerecovery from multiple node failures in mobile sensor net-worksrdquo in Proceedings of the 2010 IEEE 35th Conference onLocal Computer Networks (LCN) Denver CO USA October2010

[18] K Akkaya A immapuram F Senel and S UludagldquoDistributed recovery of actor failures in wireless sensor andactor networksrdquo in Proceedings of the IEEE Wireless Com-munications and Networking Conference Las Vegas NVUSA March 2008

[19] K Akkaya I F Senturk and S Vemulapalli ldquoHandling large-scale node failures in mobile sensorrobot networksrdquo Journalof Network and Computer Applications vol 36 no 1pp 195ndash210 2013

[20] Y K Joshi and M Younis ldquoExploiting skeletonization torestore connectivity in a wireless sensor networkrdquo ComputerCommunications vol 75 no 1 pp 97ndash107 2016

[21] X Wang L Xu S Zhou and W Wu ldquoHybrid recoverystrategy based on random terrain in wireless sensor net-worksrdquo Scientific Programming vol 2017 Article ID 580728919 pages 2017

[22] X Liu ldquoSurvivability-aware connectivity restoration forpartitioned wireless sensor networksrdquo IEEE CommunicationsLetters vol 21 no 11 pp 2444ndash2447 2017

[23] A Wichmann T Korkmaz and A S Tosun ldquoRobot controlstrategies for task allocation with connectivity constraints inwireless sensor and robot networksrdquo IEEE Transactions onMobile Computing vol 17 no 6 pp 1429ndash1441 2017

[24] M Cobanlar V KhalilpourAkram D Orhan and B TavlildquoAnalysis of the tradeoff between network lifetime andconnectivity in WSNsrdquo in Proceedings of the 2018 26thTelecommunications Forum (TELFOR) pp 1ndash4 BelgradeSerbia November 2018

[25] P Chanak I Banerjee and R S Sherratt ldquoEnergy-awaredistributed routing algorithm to tolerate network failure inwireless sensor networksrdquo Ad Hoc Networks vol 56pp 158ndash172 2017

[26] Y K Joshi and Y Mohamed ldquoAutonomous recovery from amulti-node failure in wireless sensor networkrdquo in Proceedingsof the IEEE Global Communications Conference (GLOBECOM)Anaheim CA USA December 2012

[27] N Tamboli and M Younis ldquoCoverage-aware connectivityrestoration in mobile sensor networksrdquo Journal of Networkand Computer Applications vol 33 no 4 pp 363ndash374 2010

[28] H Essam M Younis and E Shaaban ldquoMinimum cost flowsolution for tolerating multiple node failures in wirelesssensor networksrdquo in Proceedings of the 2015 IEEE In-ternational Conference on Communications (ICC) pp 6475ndash6480 London UK June 2015


International Journal of

AerospaceEngineeringHindawiwwwhindawicom Volume 2018

RoboticsJournal of

Hindawiwwwhindawicom Volume 2018


Active and Passive Electronic Components

VLSI Design



Shock and Vibration


Civil EngineeringAdvances in

Acoustics and VibrationAdvances in



Electrical and Computer Engineering

Journal of

Advances inOptoElectronics

Hindawiwwwhindawicom

Volume 2018

Hindawi Publishing Corporation httpwwwhindawicom Volume 2013Hindawiwwwhindawicom

The Scientific World Journal

Volume 2018

Control Scienceand Engineering

Journal of



Journal ofEngineeringVolume 2018

SensorsJournal of



RotatingMachinery


Modelling ampSimulationin EngineeringHindawiwwwhindawicom Volume 2018


Chemical EngineeringInternational Journal of Antennas and

Propagation




Navigation and Observation


Hindawi

wwwhindawicom Volume 2018

Advances in

Multimedia

Submit your manuscripts atwwwhindawicom

into two categories the structured and the unstructuredWSNs In the unstructured WSNs sensor nodes are denselydeployed ese sensors can be deployed in the field in an adhoc manner Once the network is deployed it remainsunattended to perform reporting and monitoring functionsIn unstructured WSNs maintenance of networks such asfailure detection and connectivity management is done in areactive manner because of random deployment of sensornodes Whereas in structured WSNs the preplanned ap-proach may be used for some or all sensors nodes e mainadvantage of structuredWSNs is the deployment of a limitednumber of sensor nodes with lower management cost andnetwork maintenance e drawback is that the deploymentof limited sensors in larger areas may result into an un-covered region [5]

WSNs have their own resource and design constraints Adesign constraint depends on the monitoring environmentand the type of application For example short-range ofcommunication limited power lower bandwidth andlimited storage and processing memory could result intodifferent designs e environment in which a WSN will bedeployed also plays a vital role in the formation of thenetwork size and network topology and the scheme of de-ployment Monitoring environment directly affects thenetwork size e indoor environment required a smallernumber of nodes for the formation of the network in alimited area while more nodes are required to form a net-work in the outdoor environment to cover larger area ead hoc deployment is better in a hostileout-of-range en-vironment where communication among sensors becomeslimited due to the obstacles in the environment [6]

Multiple sensors may fail simultaneously due to thehostileharsh environment In addition large-scale nodefailure involving multiple nodes may occur causing manydisjoint segments in a WSN Connectivity restoration is agreater challenge in this case as compared to the failure of asingle node problem In many cases simultaneous nodefailure is not contiguous yet it is expressively a much dif-ficult problem To the best of the authorsrsquo knowledge threetypes of approaches have been proposed in the recent re-search literature to reclaim multiple node failures

e first approach suggests that to restore connectivitythe topology of the network may be rearranged by reposi-tioning sensor nodes from the original positions of theWSNSuch techniques support self-healing of WSNs and are usedin a distributive manner e second approach recommendsthat multiple-relay sensor nodes should be deployed toreinstate the multiple dismember segments In the thirdapproach data is collected by the help of mobile muleswhich make trips to the critical areas and transfer that datafrom one partition to another in a WSN [7]

In context of the above sections the key contributions ofthis paper are elaborated as follows

(i) As the first contribution a technique to dynamicallyreposition the neighbouring nodes on multinodefailure is proposed to enhance network performance

(ii) e second contribution is energy efficiency of theproposed algorithm Here common neighbouring

nodes of the failure node must select one failurenode within their neighbourhood erefore thesenodes do not have to travel more than one node andthis saves energy

(iii) e third contribution is the better performance inQoS parameters like total distance travelled bynodes numbers of messages exchanged within allnodes average node relocation and reduction in thepercentage of field coverage as compared to otherbaseline techniques

e remaining paper is organised as follows Section 2highlights the relevant related work in a summarized mannerSection 3 discusses the details of the proposed algorithm forWSNs e energy model used is discussed in Section 4whereas the proposed algorithm validation and the simula-tion procedure are presented in Section 5 Section 6 concludesthe paper and proposes some possible future work

2 Related Work

e failure of the multinode problem has been addressedmany times in the literature in the recent past To handle themultinode failure problem the centralized approachesprovided better solutions ese approaches handle problemby developing a recovery schedule for multinode failure byrelocating nodes in WSNs Among these approaches in [7]the integer linear problem (ILP) is formulated for the re-covery problem In this work a nodersquos individual travellingdistance and coverage loss caused by multinode failure wereminimized by the optimization-based ILP that formed theconnected topology In this technique the position of thenode is assumed prior to the failure in WSNs In [8] atechnique grounded on the network flow transportationmodel is used where normally every single node should havethe capability to go to each destination of WSNs Here theproblem was solved by the polygon approximation modeland the formulation of mixed-integer approach is ap-proach is better from the approach provided in [9] in termsof total distance travelled However for more than 30 nodesthis technique does not measure accurately and results inerrors In [10] an alternative employment technique issuggested to reduce the number of node locations for im-proving scalability It is a practice to find the number ofpositions that promise connectivity if the relay sensors aredeployed at these locations As alternative relay sensors thecalculated locations are failed by the survival nodes in theWSN

In PADRA (partition detection and recovery algorithm)repositioned sensors are recognized by the CDS (connecteddominating set) of each partition and select the optimalnodes for recovery [11] A greedy heuristic method is used tominimize the total travelled distance of the sensors In thistechnique the nearest dominating pair of nodes are pickedand the dominate sensor is relocated to the target positione CDS of partitioned WSNs are updated until the con-nectivity is to be restored e result of this technique showsthat the heuristic method outperforms the solution andscales well as compared to [7 8] e distributed techniques





















State ofnetwork

Type ofmovement














a (sin(dlati2))2



c 2lowast a tan 2(a

radic

1 minus a

radic)

d Rlowast c

(1)




2Rc (2)


area(β) βπ

R2c minus

d

2Rc times sin

β2

1113888 1113889 (3)



πR2c

1113888 1113889 (4)











90deg

Rc

RcRc

Rc

N1 N2

p

d

q

β

α






n24n25

n26

n15 n16n17

n18

n13n12n14

n9

n11n10

n8n7

n6n1

n3n4

n5

n23n22

n21

n20

n2n19

(a)

n24n25

n26

n16

n18

n17

n14

n13n12

n9n10

n11

n8

n5n4

n23

n3

n3n4

n8n10

n6n2

n6n1

n2

n20

n19

n21n22

n15

(b)


n18

n5

n23

n11

n14

n8

n4

n22

n17

n26

n16

n2

n3

n21

n2

n20

n1n6

n9n10

n15

n12

n24n25

n19

n13

(a)

n24n25

n26

n17n16n15

n12n14

n18

n13

n13n12n9 n14

n11n9

n6

n8

n5n4

n23n22

n3

n21

n2

n20

n19

n1n6

n2

n11n8

(b)







4 Energy Model




⎧⎨

⎩ (5)























in free space



0500

100015002000250030003500400045005000

Tota

l num

ber o

f pac

kets

exch

ange

d


RIRAuROur approach


No

of m

oved

nod

es

0

100

200

300

400

500

600


RIRAuROur approach


No

of m

oved

nod

es

0

1

2

3

4

5

6

7


RIRAuROur approach







RIRAuROur approach

0

05

1

15

2

25

Tota

l dist

ance

trav

elle

d (m

)


times104







6 Conclusion


Rc = 125Rc = 100Rc = 75

Rc = 50Rc = 25

No

of m

oved

nod

es

0

2

4

6

8

10

12

14





No

of m

oved

nod

es

0

2

4

6

8

10

12

14



Reco

very

tim

e (m

in)

102030405060708090

100

RIRAuROur approach





Data Availability






Acknowledgments



References



















No ofnodes

relocated(average)



RIR 14000 2000 200 13AuR 19000 4500 700 19




















RoboticsJournal of




VLSI Design



Shock and Vibration







Journal of



Volume 2018



Volume 2018


Journal of




SensorsJournal of



RotatingMachinery





Propagation






Hindawi


Advances in

Multimedia





















State ofnetwork

Type ofmovement














a (sin(dlati2))2



c 2lowast a tan 2(a

radic

1 minus a

radic)

d Rlowast c

(1)




2Rc (2)


area(β) βπ

R2c minus

d

2Rc times sin

β2

1113888 1113889 (3)



πR2c

1113888 1113889 (4)











90deg

Rc

RcRc

Rc

N1 N2

p

d

q

β

α






n24n25

n26

n15 n16n17

n18

n13n12n14

n9

n11n10

n8n7

n6n1

n3n4

n5

n23n22

n21

n20

n2n19

(a)

n24n25

n26

n16

n18

n17

n14

n13n12

n9n10

n11

n8

n5n4

n23

n3

n3n4

n8n10

n6n2

n6n1

n2

n20

n19

n21n22

n15

(b)


n18

n5

n23

n11

n14

n8

n4

n22

n17

n26

n16

n2

n3

n21

n2

n20

n1n6

n9n10

n15

n12

n24n25

n19

n13

(a)

n24n25

n26

n17n16n15

n12n14

n18

n13

n13n12n9 n14

n11n9

n6

n8

n5n4

n23n22

n3

n21

n2

n20

n19

n1n6

n2

n11n8

(b)







4 Energy Model




⎧⎨

⎩ (5)























in free space



0500

100015002000250030003500400045005000

Tota

l num

ber o

f pac

kets

exch

ange

d


RIRAuROur approach


No

of m

oved

nod

es

0

100

200

300

400

500

600


RIRAuROur approach


No

of m

oved

nod

es

0

1

2

3

4

5

6

7


RIRAuROur approach







RIRAuROur approach

0

05

1

15

2

25

Tota

l dist

ance

trav

elle

d (m

)


times104







6 Conclusion


Rc = 125Rc = 100Rc = 75

Rc = 50Rc = 25

No

of m

oved

nod

es

0

2

4

6

8

10

12

14





No

of m

oved

nod

es

0

2

4

6

8

10

12

14



Reco

very

tim

e (m

in)

102030405060708090

100

RIRAuROur approach





Data Availability






Acknowledgments



References



















No ofnodes

relocated(average)



RIR 14000 2000 200 13AuR 19000 4500 700 19




















RoboticsJournal of




VLSI Design



Shock and Vibration







Journal of



Volume 2018



Volume 2018


Journal of




SensorsJournal of



RotatingMachinery





Propagation






Hindawi


Advances in

Multimedia















State ofnetwork

Type ofmovement














a (sin(dlati2))2



c 2lowast a tan 2(a

radic

1 minus a

radic)

d Rlowast c

(1)




2Rc (2)


area(β) βπ

R2c minus

d

2Rc times sin

β2

1113888 1113889 (3)



πR2c

1113888 1113889 (4)











90deg

Rc

RcRc

Rc

N1 N2

p

d

q

β

α






n24n25

n26

n15 n16n17

n18

n13n12n14

n9

n11n10

n8n7

n6n1

n3n4

n5

n23n22

n21

n20

n2n19

(a)

n24n25

n26

n16

n18

n17

n14

n13n12

n9n10

n11

n8

n5n4

n23

n3

n3n4

n8n10

n6n2

n6n1

n2

n20

n19

n21n22

n15

(b)


n18

n5

n23

n11

n14

n8

n4

n22

n17

n26

n16

n2

n3

n21

n2

n20

n1n6

n9n10

n15

n12

n24n25

n19

n13

(a)

n24n25

n26

n17n16n15

n12n14

n18

n13

n13n12n9 n14

n11n9

n6

n8

n5n4

n23n22

n3

n21

n2

n20

n19

n1n6

n2

n11n8

(b)







4 Energy Model




⎧⎨

⎩ (5)























in free space



0500

100015002000250030003500400045005000

Tota

l num

ber o

f pac

kets

exch

ange

d


RIRAuROur approach


No

of m

oved

nod

es

0

100

200

300

400

500

600


RIRAuROur approach


No

of m

oved

nod

es

0

1

2

3

4

5

6

7


RIRAuROur approach







RIRAuROur approach

0

05

1

15

2

25

Tota

l dist

ance

trav

elle

d (m

)


times104







6 Conclusion


Rc = 125Rc = 100Rc = 75

Rc = 50Rc = 25

No

of m

oved

nod

es

0

2

4

6

8

10

12

14





No

of m

oved

nod

es

0

2

4

6

8

10

12

14



Reco

very

tim

e (m

in)

102030405060708090

100

RIRAuROur approach





Data Availability






Acknowledgments



References



















No ofnodes

relocated(average)



RIR 14000 2000 200 13AuR 19000 4500 700 19




















RoboticsJournal of




VLSI Design



Shock and Vibration







Journal of



Volume 2018



Volume 2018


Journal of




SensorsJournal of



RotatingMachinery





Propagation






Hindawi


Advances in

Multimedia








State ofnetwork

Type ofmovement














a (sin(dlati2))2



c 2lowast a tan 2(a

radic

1 minus a

radic)

d Rlowast c

(1)




2Rc (2)


area(β) βπ

R2c minus

d

2Rc times sin

β2

1113888 1113889 (3)



πR2c

1113888 1113889 (4)











90deg

Rc

RcRc

Rc

N1 N2

p

d

q

β

α






n24n25

n26

n15 n16n17

n18

n13n12n14

n9

n11n10

n8n7

n6n1

n3n4

n5

n23n22

n21

n20

n2n19

(a)

n24n25

n26

n16

n18

n17

n14

n13n12

n9n10

n11

n8

n5n4

n23

n3

n3n4

n8n10

n6n2

n6n1

n2

n20

n19

n21n22

n15

(b)


n18

n5

n23

n11

n14

n8

n4

n22

n17

n26

n16

n2

n3

n21

n2

n20

n1n6

n9n10

n15

n12

n24n25

n19

n13

(a)

n24n25

n26

n17n16n15

n12n14

n18

n13

n13n12n9 n14

n11n9

n6

n8

n5n4

n23n22

n3

n21

n2

n20

n19

n1n6

n2

n11n8

(b)







4 Energy Model




⎧⎨

⎩ (5)























in free space



0500

100015002000250030003500400045005000

Tota

l num

ber o

f pac

kets

exch

ange

d


RIRAuROur approach


No

of m

oved

nod

es

0

100

200

300

400

500

600


RIRAuROur approach


No

of m

oved

nod

es

0

1

2

3

4

5

6

7


RIRAuROur approach







RIRAuROur approach

0

05

1

15

2

25

Tota

l dist

ance

trav

elle

d (m

)


times104







6 Conclusion


Rc = 125Rc = 100Rc = 75

Rc = 50Rc = 25

No

of m

oved

nod

es

0

2

4

6

8

10

12

14





No

of m

oved

nod

es

0

2

4

6

8

10

12

14



Reco

very

tim

e (m

in)

102030405060708090

100

RIRAuROur approach





Data Availability






Acknowledgments



References



















No ofnodes

relocated(average)



RIR 14000 2000 200 13AuR 19000 4500 700 19




















RoboticsJournal of




VLSI Design



Shock and Vibration







Journal of



Volume 2018



Volume 2018


Journal of




SensorsJournal of



RotatingMachinery





Propagation






Hindawi


Advances in

Multimedia





a (sin(dlati2))2



c 2lowast a tan 2(a

radic

1 minus a

radic)

d Rlowast c

(1)




2Rc (2)


area(β) βπ

R2c minus

d

2Rc times sin

β2

1113888 1113889 (3)



πR2c

1113888 1113889 (4)











90deg

Rc

RcRc

Rc

N1 N2

p

d

q

β

α






n24n25

n26

n15 n16n17

n18

n13n12n14

n9

n11n10

n8n7

n6n1

n3n4

n5

n23n22

n21

n20

n2n19

(a)

n24n25

n26

n16

n18

n17

n14

n13n12

n9n10

n11

n8

n5n4

n23

n3

n3n4

n8n10

n6n2

n6n1

n2

n20

n19

n21n22

n15

(b)


n18

n5

n23

n11

n14

n8

n4

n22

n17

n26

n16

n2

n3

n21

n2

n20

n1n6

n9n10

n15

n12

n24n25

n19

n13

(a)

n24n25

n26

n17n16n15

n12n14

n18

n13

n13n12n9 n14

n11n9

n6

n8

n5n4

n23n22

n3

n21

n2

n20

n19

n1n6

n2

n11n8

(b)







4 Energy Model




⎧⎨

⎩ (5)























in free space



0500

100015002000250030003500400045005000

Tota

l num

ber o

f pac

kets

exch

ange

d


RIRAuROur approach


No

of m

oved

nod

es

0

100

200

300

400

500

600


RIRAuROur approach


No

of m

oved

nod

es

0

1

2

3

4

5

6

7


RIRAuROur approach







RIRAuROur approach

0

05

1

15

2

25

Tota

l dist

ance

trav

elle

d (m

)


times104







6 Conclusion


Rc = 125Rc = 100Rc = 75

Rc = 50Rc = 25

No

of m

oved

nod

es

0

2

4

6

8

10

12

14





No

of m

oved

nod

es

0

2

4

6

8

10

12

14



Reco

very

tim

e (m

in)

102030405060708090

100

RIRAuROur approach





Data Availability






Acknowledgments



References



















No ofnodes

relocated(average)



RIR 14000 2000 200 13AuR 19000 4500 700 19




















RoboticsJournal of




VLSI Design



Shock and Vibration







Journal of



Volume 2018



Volume 2018


Journal of




SensorsJournal of



RotatingMachinery





Propagation






Hindawi


Advances in

Multimedia





n24n25

n26

n15 n16n17

n18

n13n12n14

n9

n11n10

n8n7

n6n1

n3n4

n5

n23n22

n21

n20

n2n19

(a)

n24n25

n26

n16

n18

n17

n14

n13n12

n9n10

n11

n8

n5n4

n23

n3

n3n4

n8n10

n6n2

n6n1

n2

n20

n19

n21n22

n15

(b)


n18

n5

n23

n11

n14

n8

n4

n22

n17

n26

n16

n2

n3

n21

n2

n20

n1n6

n9n10

n15

n12

n24n25

n19

n13

(a)

n24n25

n26

n17n16n15

n12n14

n18

n13

n13n12n9 n14

n11n9

n6

n8

n5n4

n23n22

n3

n21

n2

n20

n19

n1n6

n2

n11n8

(b)







4 Energy Model




⎧⎨

⎩ (5)























in free space



0500

100015002000250030003500400045005000

Tota

l num

ber o

f pac

kets

exch

ange

d


RIRAuROur approach


No

of m

oved

nod

es

0

100

200

300

400

500

600


RIRAuROur approach


No

of m

oved

nod

es

0

1

2

3

4

5

6

7


RIRAuROur approach







RIRAuROur approach

0

05

1

15

2

25

Tota

l dist

ance

trav

elle

d (m

)


times104







6 Conclusion


Rc = 125Rc = 100Rc = 75

Rc = 50Rc = 25

No

of m

oved

nod

es

0

2

4

6

8

10

12

14





No

of m

oved

nod

es

0

2

4

6

8

10

12

14



Reco

very

tim

e (m

in)

102030405060708090

100

RIRAuROur approach





Data Availability






Acknowledgments



References



















No ofnodes

relocated(average)



RIR 14000 2000 200 13AuR 19000 4500 700 19




















RoboticsJournal of




VLSI Design



Shock and Vibration







Journal of



Volume 2018



Volume 2018


Journal of




SensorsJournal of



RotatingMachinery





Propagation






Hindawi


Advances in

Multimedia






4 Energy Model




⎧⎨

⎩ (5)























in free space



0500

100015002000250030003500400045005000

Tota

l num

ber o

f pac

kets

exch

ange

d


RIRAuROur approach


No

of m

oved

nod

es

0

100

200

300

400

500

600


RIRAuROur approach


No

of m

oved

nod

es

0

1

2

3

4

5

6

7


RIRAuROur approach







RIRAuROur approach

0

05

1

15

2

25

Tota

l dist

ance

trav

elle

d (m

)


times104







6 Conclusion


Rc = 125Rc = 100Rc = 75

Rc = 50Rc = 25

No

of m

oved

nod

es

0

2

4

6

8

10

12

14





No

of m

oved

nod

es

0

2

4

6

8

10

12

14



Reco

very

tim

e (m

in)

102030405060708090

100

RIRAuROur approach





Data Availability






Acknowledgments



References



















No ofnodes

relocated(average)



RIR 14000 2000 200 13AuR 19000 4500 700 19




















RoboticsJournal of




VLSI Design



Shock and Vibration







Journal of



Volume 2018



Volume 2018


Journal of




SensorsJournal of



RotatingMachinery





Propagation






Hindawi


Advances in

Multimedia












in free space



0500

100015002000250030003500400045005000

Tota

l num

ber o

f pac

kets

exch

ange

d


RIRAuROur approach


No

of m

oved

nod

es

0

100

200

300

400

500

600


RIRAuROur approach


No

of m

oved

nod

es

0

1

2

3

4

5

6

7


RIRAuROur approach







RIRAuROur approach

0

05

1

15

2

25

Tota

l dist

ance

trav

elle

d (m

)


times104







6 Conclusion


Rc = 125Rc = 100Rc = 75

Rc = 50Rc = 25

No

of m

oved

nod

es

0

2

4

6

8

10

12

14





No

of m

oved

nod

es

0

2

4

6

8

10

12

14



Reco

very

tim

e (m

in)

102030405060708090

100

RIRAuROur approach





Data Availability






Acknowledgments



References



















No ofnodes

relocated(average)



RIR 14000 2000 200 13AuR 19000 4500 700 19




















RoboticsJournal of




VLSI Design



Shock and Vibration







Journal of



Volume 2018



Volume 2018


Journal of




SensorsJournal of



RotatingMachinery





Propagation






Hindawi


Advances in

Multimedia







in free space



0500

100015002000250030003500400045005000

Tota

l num

ber o

f pac

kets

exch

ange

d


RIRAuROur approach


No

of m

oved

nod

es

0

100

200

300

400

500

600


RIRAuROur approach


No

of m

oved

nod

es

0

1

2

3

4

5

6

7


RIRAuROur approach







RIRAuROur approach

0

05

1

15

2

25

Tota

l dist

ance

trav

elle

d (m

)


times104







6 Conclusion


Rc = 125Rc = 100Rc = 75

Rc = 50Rc = 25

No

of m

oved

nod

es

0

2

4

6

8

10

12

14





No

of m

oved

nod

es

0

2

4

6

8

10

12

14



Reco

very

tim

e (m

in)

102030405060708090

100

RIRAuROur approach





Data Availability






Acknowledgments



References



















No ofnodes

relocated(average)



RIR 14000 2000 200 13AuR 19000 4500 700 19




















RoboticsJournal of




VLSI Design



Shock and Vibration







Journal of



Volume 2018



Volume 2018


Journal of




SensorsJournal of



RotatingMachinery





Propagation






Hindawi


Advances in

Multimedia






6 Conclusion


Rc = 125Rc = 100Rc = 75

Rc = 50Rc = 25

No

of m

oved

nod

es

0

2

4

6

8

10

12

14





No

of m

oved

nod

es

0

2

4

6

8

10

12

14



Reco

very

tim

e (m

in)

102030405060708090

100

RIRAuROur approach





Data Availability






Acknowledgments



References



















No ofnodes

relocated(average)



RIR 14000 2000 200 13AuR 19000 4500 700 19




















RoboticsJournal of




VLSI Design



Shock and Vibration







Journal of



Volume 2018



Volume 2018


Journal of




SensorsJournal of



RotatingMachinery





Propagation






Hindawi


Advances in

Multimedia



Data Availability






Acknowledgments



References



















No ofnodes

relocated(average)



RIR 14000 2000 200 13AuR 19000 4500 700 19




















RoboticsJournal of




VLSI Design



Shock and Vibration







Journal of



Volume 2018



Volume 2018


Journal of




SensorsJournal of



RotatingMachinery





Propagation






Hindawi


Advances in

Multimedia




















RoboticsJournal of




VLSI Design



Shock and Vibration







Journal of



Volume 2018



Volume 2018


Journal of




SensorsJournal of



RotatingMachinery





Propagation






Hindawi


Advances in

Multimedia




RoboticsJournal of




VLSI Design



Shock and Vibration







Journal of



Volume 2018



Volume 2018


Journal of




SensorsJournal of



RotatingMachinery





Propagation






Hindawi


Advances in

Multimedia


Documents

Quality of Service-Based Node Relocation Technique for