# A Novel Efficient Data Gathering Algorithm for Disconnected Sensor Networks Based on Mobile Edge Computing

Authors: Zeyu Sun; Lan Lan; Cao Zeng; Guisheng Liao
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Employing mobile elements is an efficient solution to the performance improvement of wireless sensor networks (WSNs). We propose an efficient data gathering mechanism for disconnected WSNs with rendezvous points (DGM-RPs). The mobile sink traverses the entire network and stops only at the rendezvous points (RPs) while gathers the data from sensors in every disconnected segment. In this paper, mobile sinks perform the task of edge computing and alleviate the load of upper cloud. We measure the shape of disconnected segments, layering them by use of the convex hull, and then design the travelling path of the mobile sink to minimize the travel latency to visit all disconnected segments. At least one RPs will be selected in a segment firstly, and then, on this basis, we consider the distribution density of sensor nodes and the location of the RPs already exist to adding new RPs, which make good use of the margin to reducing the energy consumption and prolong the network lifetime.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) have been playing an increasingly important role in wide-ranging applications, such as military, agriculture, home automation, medical treatment, environmental monitoring, and smart transportation [1–3]. Energy conservation is the most important thing in WSNs, since sensor nodes’ capabilities are sustained until their batteries are depleted. In multihop communications due to heavy overload of relaying messages, the nodes which are near the sink have a tendency to die earlier than those which are farther away.Mobile sink implicitly provides load balancing without extra effort, using mobile sink walks along the WSN to gather data instead of multihop transmission to the sink can dramatically reduce the energy consumption of sensors, which prolongs the lifetime of networks [4, 5]. Sparse and disconnected networks can be better handled with mobile sinks. In WSNs, the delivery latency is defined as the time mobile sink takes to travel around the network to collect data. However, visiting all sensors means a high delay; hence, rendezvous points are selected. Mobile sink is supposed to only visit rendezvous points (RPs) nodes when a delay is restricted. In theoretical research, we require networking a set of disconnected segments within relatively short time duration. Such as sensor nodes deployed in the forest, due to weather or natural disasters and other reasons, some sensor nodes have been damaged, resulting in the network is divided into several segments of nonconnected, and most of the sensor nodes can work properly [6–9]. Re-deployment of the network will bring a huge cost; the use of mobile sink with a shorter delay in the collection of data in disconnected segments has become an ideal remedy [10–12]. Network topologies are various; it is more realistic and efficient to design the travelling path of the mobile sink dynamically according to the distribution of sensor nodes.In this paper, we consider the problem of planning the travelling path of a mobile sink in a disconnected network and reducing the overload of sensor nodes to maximize network lifetimeFirstly, at least one RPs is selected in each disconnected network to send the data collected by all sensor nodes to the mobile sink. Secondly, we consider distributing sensor nodes location information and add new RPs nodes to reduce the energy consumption of sensor node.The contribution of this work can be summarized as follows:(1)
According to specific business requirements, we planned the travelling paths of the mobile sink dynamically. Length of paths was compressed maximally when the delay limit was critical, and the number of RPs was increased to reduce energy consumption and extend the lifetime of the network if the delay limit was relatively loose(2)
Instead of using a simplifying model to abstract a disconnected segment into one point, or to use sensor nodes located on the boundary of the segment to represent it, we took full account of the shapes and sizes of segments for their varieties, which more conforms actual applications(3)
With the assist of convex hull scanning, the RPs were placed in corresponding segments of each layer according to the order of outside-to-inside, and shapes of disconnected segments were taken full advantages to reduce the length of paths meanwhile(4)
Under the condition that the mobile SINK node can reach all inter-segment networks and the minimum delay, we consider increasing the number of PRs through the distribution status of sensor nodes and the length of remaining paths to reduce the network energy and prolong the network lifetime


## 2. Related Work

Recent works have exploited the use of mobile sink in data collection. There are many approaches to the problem of data collection in WSNs with mobile sinks. The paper [13] proposes a static and dynamic conversion scheme to replace faulty nodes. The faulty node is replaced with the adjacent redundant node, and the mobile node locates its best position through simple geometric operations to ensure the connectivity of the network. The paper [14] proposes a path planning strategy of mobile data collection, called the dual approximation of anchor points (DAAP). It is especially designed for disconnected WSNs where sensor nodes are scattered in multiple isolated segments, and it has the least calculation complexity compared with other existing works. The paper [15] proposed prediction model for lost packets based on data reconstruction (PM-LPDR). The lost packet on lossy links can be modeled as a random loss during the transmission, and the matching type of the lost packets can be further predicted. Retransmission is adopted for data recovery when a random packet loss is predicted, while prediction algorithms based on time sequences can be employed for data recovery when a random packet loss cannot be predicted. The paper [16] proposes the optimal deployment strategy of gateway nodes. This strategy can solve the problem of gateway node redundancy, construct fault tolerance with the least number of gateway nodes, and give an approximate solution algorithm. The paper [17] discusses the distributed fault-tolerant clustering algorithm of sensor networks, which is used to construct the k-order dominance set subgraph of wireless sensor networks to complete the optimization of the data transmission link. The paper [18] proves that for any given communication link, constructing a k-connected network topology, there is an approximate solution optimal algorithm, so that the boundary does not exceed On2. On this basis, a greedy distributed algorithm is proposed, and mobile nodes are used to optimize the entire network link. The paper [19] discusses adding appropriate mobile nodes to a wireless sensor network with a two-level cluster structure, so that each node of the network can communicate with at least two gateway nodes, thereby completing a multinode connectivity. The paper [20] is an adaptive clustering algorithm that is executed periodically. The algorithm is divided into two phases in each cycle, namely, the cluster establishment phase and the data stable communication phase. In the cluster establishment phase, adjacent nodes dynamically form clusters and randomly generate cluster heads; in the data stable communication phase, the hydrogen data of the nodes in the cluster is sent to the cluster head, and the cluster head performs data fusion and sends the result to the sink node. The paper [21] proposes a backup survival routing algorithm. The algorithm transmits multiple copies of the same data on multiple independent paths. When the node transmission fails, the original path is repaired or a new path is found to ensure the normal transmission of data; in the case of multipath, the algorithm uses encryption technology to implement redundant routing based on security and diversity and has good fault tolerance. The paper [22] discusses the communication method between the cluster head and the base station and specific methods to improve the efficiency of data transmission. Multipath is used to ensure that the information in the cluster can be reliably transmitted to the base station. By establishing multihop communication between the cluster head and the base station, part of the cluster head energy can be saved, thereby extending the network lifetime.


## 3. Materials and Methods

As shown in Figure1, we consider heterogeneous WSNs usually deployed in areas that are dangerous or even unreachable to humans, which consist of many disconnected segments with some static sensor nodes. We have some assumptions before describing deep:
(1)
Sensor nodes have a fixed data transmission range(2)
The number, shape, and size of the disconnected segments all three are random(3)
In every disconnected segment, sensor nodes are deployed on a plane randomly, and their positions can be known(4)
Disconnected segments are isolated; sensor nodes deployed in different segments cannot communicate with each other by multihop transmission(5)
Only one mobile sink can be used for data collection. The mobile sink moves at a fixed speed(6)
Sensor nodes’ routing time and the communication time can be negligible, as compared with the mobile sink’s travelling time(7)
Each RPs node has a fixed storage capacity to buffer collected data; data can be collected when a mobile sink visits the RPs nodes in a specific time intervalFigure 1
Typical network topology.We considered on both aspects of reducing latency and decreasing overall-network energy consumption. Commonly, an application scenario will be accompanied by a specific latency constraint, which brings a limit to length of path of the mobile sink [23–25]. We considered networks in two cases. Some have a small number of segments and a simple topology, and others have a large number of segments and a complex topology. For those simple, we used the center point to select the RP in each segment and plan the mobile sink’s travelling strategy by running classical TSP algorithm quickly [26–28]. For those complexes, our approach was divided into two steps, including selection of first RP in every disconnected segment and using remaining available path length to add new RPs. Meanwhile, the first step included using convex hull to stratify the network and organizing the path. The second step included assigning the available path lengths proportionally to each disconnected segment and selecting RPs according to weight, which helped reducing network energy consumption.


### 3.1. Determining the Center Point

We defined “auxiliary node” for every segment. An auxiliary node is a sensor node that has the least sum of distances to all nodes in other segments. For a nodei in segment k, its sum Si can be determined by formula (1), where j denotes all nodes that are not in segment k. For each segment, we denoted it a number i; and all nodes in this segment formed a set, which was symbolized Vi. Then, we acquire auxiliary node of every segment, after running the algorithm as shown in Algorithm 1. After we found the coordinates of auxiliary nodes, we define the center point of the network with symbol C0, whose coordinates (x, y) could be calculated by formula (2). Actually, it is the average coordinates of auxiliary nodes of all segments [29, 30]. The set-up of the center point can reduce the influence of shapes of segments on the mobile sink’s path length, so we can use the center point to find a short path. If we follow Figure 2 to change the shape and size of one of the segments, the shortest path lengths required to access the four segments in Figure 2(a) and Figure 2(b) are the same.
(1)Si=∑jdiji∈k,j∉k,(2)x,y=1N∑i=1Nxi,1N∑i=1Nyi.Algorithm 1: Determining the auxiliary node of segment i.
Input: Vi, the set of sensor nodes in segment idjm, the distance between node j and node mSize(·), get the element number of setOutput: Ri, the auxiliary node of segmentibeginforj←1to Size (Vi) dow ←0min ←+∞fork ←1 to Nandk≠idoform ←1 to Size (Vk) dow ← w + djmend forend forifw< min thenmin =wRi= jend ifend forendFigure 2
The shortest path of the four segments. (a) The case with similar segments. (b) The case with large difference of segments.
(a)(b)The node nearest to the center point will be selected as a RP in each segment. For a network with a small number of segments and a simple topology, a travelling path for the mobile sink can be quickly built. The solution is particularly applicable to scenes with harsh latency. As shown in Figure3(a), the nodes in segments are usually considered as points of uniform quality, and their centers of gravity will be calculated and then be selected as RPs, when people uses the traditional solution, which is inefficient and barely applicable to scenes with harsh latency. As comparison, our approach satisfies the requirement of latency by setting up the center point, which is shown in Figure 3(b). For a network with large numbers of nodes and complex topologies, we perform subsequent steps to adjust the selected RPs in each segment and add new RPs without exceeding the given latency constraint.Figure 3
Path scheme for a network with simple topology. (a) Traditional approach. (b) Approach with the center point.
(a)(b)


### 3.2. Determining the First RP in Each Disconnected Segment

In the following sections, we will explain how to plan the travelling path for the mobile sink in networks with large numbers of nodes and complex topologies, while the shape and size of segments are usually irregular. The first RPs in every segment will be set up primarily as described in Section3.1. There is one and only one RPs in each segment; after the subsequent steps, the selection of the RPs in some segments will be adjusted. The selection of RPs do not need to be adjusted in some segments which are more possible located near the boundary of the network, and these segments are called as “remote segments.” Specifically, whether a segment is a remote segment is determined by the stratification of the entire network, and all segments of the first layer are treated as remote segments. For these remote segments, selecting nodes near the boundary of segments can help reducing length of travelling path of mobile sinks, such as seg1, seg2, and seg4 in Figure 4. On the other hand, the mobile sink is needed to access three segments successively, and positions of RPs in the first segment and the third segment are known. The known two RPs can be used to determine the RPs of the second segment. Obviously, choosing the node that has minimum sum of distances to the known two RPs can reduce the length of mobile sink’s path maximally. As shown in Figure 5, if the positions of RPs in seg1 and seg3 are known, node n will be chosen as the RPs in seg2. Our approach combines two main ideas mentioned above; that is, firstly the mobile sink draws a polygon by accessing all remote segments [31, 32]. After that, all other segments except the remote segments refer to the polygon to select the RPs so the entire path is shrunk, which helps reducing the path length. In order to distinguish which segments can be treated as remote segments and form the polygon, which segments can be within the polygon, the center point and the method of convex hull scanning are used to stratify the whole network.Figure 4
Selecting RPs located near the boundary.Figure 5
Refer to the known RPs to select RPs.Each segment contains several sensor nodes. To facilitate the stratification of the entire network, a representative node will be selected in each segment to represent the segment. The positional relationship between segment and other segments should be considered in our selection strategy of representative node in a segment, and the center point also can be used as a reference. The first RPs in each segment will be defined as a representative node, and all representative nodes form a collection of points. Given a set of points on a plane, Graham scan can be used to find the corresponding convex hull. More specifically, given a point set, the point was treated as starting point whosex coordinate or the y coordinate is the smallest. The other points are connected to the starting point to form a polar angle, and all points in the set are sorted according to the polar angle. A stack can be used for calculating the convex hull. Each point in the set will be stacked once, and finally, the points on the convex hull will be left on the stack. There are a total of N segments, one of which is represented by the symbol i; the representative node of the segment is represented by the symbol Ai; and the set of points of all representative nodes is denoted by the symbol A, and then, A=A1,A2,⋯,Ai⋯,AN. The corresponding convex hull of point set A can be found, which is symbol as A′, and A′ is also a point set consisting of representative nodes. We retrieved all the elements in A′ and mark their corresponding segments as the same layer. Take the difference set of A and A′; repeat the above iterative process; and ultimately, the entire network is divided into several levels. The stratify algorithm is summarized in Algorithm 2.Algorithm 2: Stratifying network.
Input: A=A1,A2,⋯,Ai⋯,AN, set of representative nodeA′, a set represent the convex hull of AOutput: the layer of disconnected segmentsbeginlayer ← 1whileA is not emptyA′← find the convex hull ofAA←A−A′for each i∈A′domark segment i with layerend forlayer++end whileendThrough the stratification, the most peripheral segments, which were marked as the first layer of the network, can be found. Accessing all the RPs in the segments of the current layer can form a closed path. Each segment of the next layer will be considered, and the node that has the minimum sum of distances from itself to the two endpoints of the path lines will be adjusted as the RPs, where the path lines include all the lines that make up the closed path. In accordance with the rules described above, we can acquire the position of first RP of each segment. Given the set of RPs, the path design problem is modeled as the TSP, and the mobile sink’s travelling path can be acquired by 2-opt algorithm, which is a simple local search algorithm first proposed in [14] for solving the TSP. The main idea behind it is to take a route that crosses over itself and reorder it so that it does not. The advantage of the 2-opt algorithm is easy understanding, and it can help us quickly find the approximate solution in On2 time, where n is the number of points.After we got the mobile sink’s travelling path, we made further optimization to compress the path. Assuming that the RPs is visited in the order ofPi, Pj, and P′, which are in segmenti, k, and j, respectively. Pi and Pj are connected as a line segment to check the nodes in segmentk to see if there is a node P′ that is more appropriate than P′, which means the distance from P′ to line Pi∗Pjis closer than P′. The path establishment and optimization algorithm are described in Algorithm 3; after the above stages, a relatively short path is found to ensure that each disconnected segments can be visited.Algorithm 3: Path organization.
Input: V=V1,V2,⋯,VN, set of sensor nodes in segmentsA=A1,A2,⋯Ai⋯,AN, set of representative nodeMAX_LAYER, the max layer of disconnected segmentsI, a set represent the visit order of nodes in PIi, the i-th element in the setSize (·), get the size of setDis (p, l), calculate the distance from the point p to the line segment lSegment(·), find the segment in which the node distributedTSP(·), run TSP algorithm to determine the path lengtha∗b, line segment whose ends are node a and node b, respectivelyOutput: P=P1,P2,⋯,PN, set of RPsprocedure PATH_ESTABLISHMENTbeginfind segments of the first layer, add correspondingAi to PcurrentLayer ← 2while currentLayer < MAX_LAYERrun TSP algorithm to determine the visit order of nodes inPconnect adjacent visits to form path linescheck all segments whose layer are currentLayer+1, add the node toP, the node should has the minimum sum of distances from itself to the two endpoints of the path lines in its segmentscurrentLayer++end whileendend procedureprocedure PATH_OPTIMIZATIONbegindopreLen ← TSP (P)optimize ← falseI← get the visit order of nodes in PI←I∪{I1,I2}Loop:fork =1 to Size (I)-2 doform = 1 to Size(VSegmentI+1) doif Dis (m, Ik∗Ik+2) < Dis (PSegmentI+1, Ik∗Ik+2) thenif TSP P∪m–PSegment(I+1) < pre_Len thenP⟵P∪m–PSegment(I+1)optimize ← truebreak Loopend ifend ifend forend forI⟵I−I1−I2while optimize = trueendend procedure


### 3.3. RPs Analysis and Realization

The various steps of our approach are explained using a detail example in Figure6. The network consists of several disconnected segments, as shown in Figure 6(a). The “auxiliary nodes” are shown in Figure 6(b). Firstly, the center point and the representative node in each segment will be found. The center point is marked as a five-pointed star, and the representative node in each segment is shown in Figure 6(c). All representative nodes form a collection of points, Graham scan is used to find the corresponding convex hull, and one convex hull can split a layer of network. Figure 6(d) shows that the network is divided into three layers, while the outermost layer, the middle layer, and the innermost layer have 4, 3, and 2 segments, respectively. After stratification, the representative node in each segment will be selected as the first RPs, and then, the selection of RPs will be checked and modified layer by layer. For example, as Figure 6(e) shows, connecting all segments of the first layer forms the path lines; segments of layer two are checked to find a new RP, which has the minimum sum of distances from itself to the two endpoints of the path lines. After the above steps, each segment had RPs; the mobile sink’s travelling path obtained by TSP algorithm is shown in Figure 6(f), while Figure 6(g) shows the result of our optimization step of the path. Figure 6(h) shows that the detection rectangle representing the distribution boundary of the node can be found, which will be divided into several cells. The total length of the path cannot exceed a certain value, and the remaining available paths are fully utilized to expand the new RPs.Figure 6
Determines RPs and path: (a) the network topology; (b) the RPs in every segment; (c) the selection of the closest nodes and the center point; (d) scan the convex hull and stratify the network; (e) modify the selection of RPs in the segments except the remote segments; (f) the mobile sink’s travelling path obtained by TSP algorithm; (g) the mobile sink’s travelling path after optimizing; and (h) divide the whole network into several cells.
(a)(b)(c)(d)(e)(f)(g)(h)


### 3.4. Using the Available Path Length to Add the New RPs

After the above steps, a short path for the mobile sink has been planned to visit all disconnected segments, which has only one RP in each segment. If the delay requirement is looser, the number of RPs will increase, and the path will be expanded to reduce the energy consumption of the whole network, which includes assigning available path lengths proportionally to each disconnected segment and weighted selection of RPs.The numbers of nodes distributed in disconnected segments are different. If a small number of RPs is selected in a segment with many nodes, then some of the nodes need to send the data to the RPs by long-distance multihop transmission, which goes against the principle of extending the network life because of increasing the energy consumption of the network. To set up more RPs in the segments with many nodes is a reasonable program; therefore, the available remaining path length will be allocated by the number of nodes in the segment. For example, the current path length of the mobile sink isL, and the total path length is limited to Llimit, and then, the available remaining path length of segment iis determined by
(3)Li=SizeVi∑k=1NSizeVk×Llimit−L,where function Size· can get the number of elements in a set and Vi is the set of sensor nodes distributed in segment i.As described in the system model, each node knows its own position. Nodes’x coordinates are X1,X2,⋯,XN, and their y coordinates are Y1,Y2,⋯,YN, respectively. Then, the distribution boundaries of the nodes are within a “detection rectangle,” where the bottom left corner of the rectangle is located at (minX1,X2,⋯,XN, minY1,Y2,⋯,YN) and the upper right corner of the rectangle is located at (maxX1,X2,⋯,XN, maxY1,Y2,⋯,YN). We divide the rectangle into α2 cells, with α to represent the granularity of the division. Put it another way, the rectangle is divided into α parts both vertically and horizontally. Next, for each segment, the weight of the nodes will be calculated according to formula (4), and the nodes will be sorted in descending order of weight. In each round, a new RPs will be added in order. If the new RPs does not cause the path length to exceed the limit, it will be retained. The factor β in formula (4) indicates the number of nodes in the cell to which the node belongs and reflects the density of the nodes. On the other hand, it is not appropriate for a large number of RPs to come together; new RPs should have some distance from the existing RPs; therefore, the factor φ is proportional to the number of RPs that already exist in the cell to which the node belongs.
(4)W=β−φ.Finally, we acquire the final RPs set and the corresponding mobile sink’s travelling path by the algorithm described in Algorithm3. The segments with more nodes will set up more RPs. The selection of the RPs strategy includes the consideration of segment size, shape, and distribution of nodes, which is conducive to reducing network energy consumption and extend the network life.


## 3.1. Determining the Center Point

We defined “auxiliary node” for every segment. An auxiliary node is a sensor node that has the least sum of distances to all nodes in other segments. For a nodei in segment k, its sum Si can be determined by formula (1), where j denotes all nodes that are not in segment k. For each segment, we denoted it a number i; and all nodes in this segment formed a set, which was symbolized Vi. Then, we acquire auxiliary node of every segment, after running the algorithm as shown in Algorithm 1. After we found the coordinates of auxiliary nodes, we define the center point of the network with symbol C0, whose coordinates (x, y) could be calculated by formula (2). Actually, it is the average coordinates of auxiliary nodes of all segments [29, 30]. The set-up of the center point can reduce the influence of shapes of segments on the mobile sink’s path length, so we can use the center point to find a short path. If we follow Figure 2 to change the shape and size of one of the segments, the shortest path lengths required to access the four segments in Figure 2(a) and Figure 2(b) are the same.
(1)Si=∑jdiji∈k,j∉k,(2)x,y=1N∑i=1Nxi,1N∑i=1Nyi.Algorithm 1: Determining the auxiliary node of segment i.
Input: Vi, the set of sensor nodes in segment idjm, the distance between node j and node mSize(·), get the element number of setOutput: Ri, the auxiliary node of segmentibeginforj←1to Size (Vi) dow ←0min ←+∞fork ←1 to Nandk≠idoform ←1 to Size (Vk) dow ← w + djmend forend forifw< min thenmin =wRi= jend ifend forendFigure 2
The shortest path of the four segments. (a) The case with similar segments. (b) The case with large difference of segments.
(a)(b)The node nearest to the center point will be selected as a RP in each segment. For a network with a small number of segments and a simple topology, a travelling path for the mobile sink can be quickly built. The solution is particularly applicable to scenes with harsh latency. As shown in Figure3(a), the nodes in segments are usually considered as points of uniform quality, and their centers of gravity will be calculated and then be selected as RPs, when people uses the traditional solution, which is inefficient and barely applicable to scenes with harsh latency. As comparison, our approach satisfies the requirement of latency by setting up the center point, which is shown in Figure 3(b). For a network with large numbers of nodes and complex topologies, we perform subsequent steps to adjust the selected RPs in each segment and add new RPs without exceeding the given latency constraint.Figure 3
Path scheme for a network with simple topology. (a) Traditional approach. (b) Approach with the center point.
(a)(b)


## 3.2. Determining the First RP in Each Disconnected Segment

In the following sections, we will explain how to plan the travelling path for the mobile sink in networks with large numbers of nodes and complex topologies, while the shape and size of segments are usually irregular. The first RPs in every segment will be set up primarily as described in Section3.1. There is one and only one RPs in each segment; after the subsequent steps, the selection of the RPs in some segments will be adjusted. The selection of RPs do not need to be adjusted in some segments which are more possible located near the boundary of the network, and these segments are called as “remote segments.” Specifically, whether a segment is a remote segment is determined by the stratification of the entire network, and all segments of the first layer are treated as remote segments. For these remote segments, selecting nodes near the boundary of segments can help reducing length of travelling path of mobile sinks, such as seg1, seg2, and seg4 in Figure 4. On the other hand, the mobile sink is needed to access three segments successively, and positions of RPs in the first segment and the third segment are known. The known two RPs can be used to determine the RPs of the second segment. Obviously, choosing the node that has minimum sum of distances to the known two RPs can reduce the length of mobile sink’s path maximally. As shown in Figure 5, if the positions of RPs in seg1 and seg3 are known, node n will be chosen as the RPs in seg2. Our approach combines two main ideas mentioned above; that is, firstly the mobile sink draws a polygon by accessing all remote segments [31, 32]. After that, all other segments except the remote segments refer to the polygon to select the RPs so the entire path is shrunk, which helps reducing the path length. In order to distinguish which segments can be treated as remote segments and form the polygon, which segments can be within the polygon, the center point and the method of convex hull scanning are used to stratify the whole network.Figure 4
Selecting RPs located near the boundary.Figure 5
Refer to the known RPs to select RPs.Each segment contains several sensor nodes. To facilitate the stratification of the entire network, a representative node will be selected in each segment to represent the segment. The positional relationship between segment and other segments should be considered in our selection strategy of representative node in a segment, and the center point also can be used as a reference. The first RPs in each segment will be defined as a representative node, and all representative nodes form a collection of points. Given a set of points on a plane, Graham scan can be used to find the corresponding convex hull. More specifically, given a point set, the point was treated as starting point whosex coordinate or the y coordinate is the smallest. The other points are connected to the starting point to form a polar angle, and all points in the set are sorted according to the polar angle. A stack can be used for calculating the convex hull. Each point in the set will be stacked once, and finally, the points on the convex hull will be left on the stack. There are a total of N segments, one of which is represented by the symbol i; the representative node of the segment is represented by the symbol Ai; and the set of points of all representative nodes is denoted by the symbol A, and then, A=A1,A2,⋯,Ai⋯,AN. The corresponding convex hull of point set A can be found, which is symbol as A′, and A′ is also a point set consisting of representative nodes. We retrieved all the elements in A′ and mark their corresponding segments as the same layer. Take the difference set of A and A′; repeat the above iterative process; and ultimately, the entire network is divided into several levels. The stratify algorithm is summarized in Algorithm 2.Algorithm 2: Stratifying network.
Input: A=A1,A2,⋯,Ai⋯,AN, set of representative nodeA′, a set represent the convex hull of AOutput: the layer of disconnected segmentsbeginlayer ← 1whileA is not emptyA′← find the convex hull ofAA←A−A′for each i∈A′domark segment i with layerend forlayer++end whileendThrough the stratification, the most peripheral segments, which were marked as the first layer of the network, can be found. Accessing all the RPs in the segments of the current layer can form a closed path. Each segment of the next layer will be considered, and the node that has the minimum sum of distances from itself to the two endpoints of the path lines will be adjusted as the RPs, where the path lines include all the lines that make up the closed path. In accordance with the rules described above, we can acquire the position of first RP of each segment. Given the set of RPs, the path design problem is modeled as the TSP, and the mobile sink’s travelling path can be acquired by 2-opt algorithm, which is a simple local search algorithm first proposed in [14] for solving the TSP. The main idea behind it is to take a route that crosses over itself and reorder it so that it does not. The advantage of the 2-opt algorithm is easy understanding, and it can help us quickly find the approximate solution in On2 time, where n is the number of points.After we got the mobile sink’s travelling path, we made further optimization to compress the path. Assuming that the RPs is visited in the order ofPi, Pj, and P′, which are in segmenti, k, and j, respectively. Pi and Pj are connected as a line segment to check the nodes in segmentk to see if there is a node P′ that is more appropriate than P′, which means the distance from P′ to line Pi∗Pjis closer than P′. The path establishment and optimization algorithm are described in Algorithm 3; after the above stages, a relatively short path is found to ensure that each disconnected segments can be visited.Algorithm 3: Path organization.
Input: V=V1,V2,⋯,VN, set of sensor nodes in segmentsA=A1,A2,⋯Ai⋯,AN, set of representative nodeMAX_LAYER, the max layer of disconnected segmentsI, a set represent the visit order of nodes in PIi, the i-th element in the setSize (·), get the size of setDis (p, l), calculate the distance from the point p to the line segment lSegment(·), find the segment in which the node distributedTSP(·), run TSP algorithm to determine the path lengtha∗b, line segment whose ends are node a and node b, respectivelyOutput: P=P1,P2,⋯,PN, set of RPsprocedure PATH_ESTABLISHMENTbeginfind segments of the first layer, add correspondingAi to PcurrentLayer ← 2while currentLayer < MAX_LAYERrun TSP algorithm to determine the visit order of nodes inPconnect adjacent visits to form path linescheck all segments whose layer are currentLayer+1, add the node toP, the node should has the minimum sum of distances from itself to the two endpoints of the path lines in its segmentscurrentLayer++end whileendend procedureprocedure PATH_OPTIMIZATIONbegindopreLen ← TSP (P)optimize ← falseI← get the visit order of nodes in PI←I∪{I1,I2}Loop:fork =1 to Size (I)-2 doform = 1 to Size(VSegmentI+1) doif Dis (m, Ik∗Ik+2) < Dis (PSegmentI+1, Ik∗Ik+2) thenif TSP P∪m–PSegment(I+1) < pre_Len thenP⟵P∪m–PSegment(I+1)optimize ← truebreak Loopend ifend ifend forend forI⟵I−I1−I2while optimize = trueendend procedure


## 3.3. RPs Analysis and Realization

The various steps of our approach are explained using a detail example in Figure6. The network consists of several disconnected segments, as shown in Figure 6(a). The “auxiliary nodes” are shown in Figure 6(b). Firstly, the center point and the representative node in each segment will be found. The center point is marked as a five-pointed star, and the representative node in each segment is shown in Figure 6(c). All representative nodes form a collection of points, Graham scan is used to find the corresponding convex hull, and one convex hull can split a layer of network. Figure 6(d) shows that the network is divided into three layers, while the outermost layer, the middle layer, and the innermost layer have 4, 3, and 2 segments, respectively. After stratification, the representative node in each segment will be selected as the first RPs, and then, the selection of RPs will be checked and modified layer by layer. For example, as Figure 6(e) shows, connecting all segments of the first layer forms the path lines; segments of layer two are checked to find a new RP, which has the minimum sum of distances from itself to the two endpoints of the path lines. After the above steps, each segment had RPs; the mobile sink’s travelling path obtained by TSP algorithm is shown in Figure 6(f), while Figure 6(g) shows the result of our optimization step of the path. Figure 6(h) shows that the detection rectangle representing the distribution boundary of the node can be found, which will be divided into several cells. The total length of the path cannot exceed a certain value, and the remaining available paths are fully utilized to expand the new RPs.Figure 6
Determines RPs and path: (a) the network topology; (b) the RPs in every segment; (c) the selection of the closest nodes and the center point; (d) scan the convex hull and stratify the network; (e) modify the selection of RPs in the segments except the remote segments; (f) the mobile sink’s travelling path obtained by TSP algorithm; (g) the mobile sink’s travelling path after optimizing; and (h) divide the whole network into several cells.
(a)(b)(c)(d)(e)(f)(g)(h)


## 3.4. Using the Available Path Length to Add the New RPs

After the above steps, a short path for the mobile sink has been planned to visit all disconnected segments, which has only one RP in each segment. If the delay requirement is looser, the number of RPs will increase, and the path will be expanded to reduce the energy consumption of the whole network, which includes assigning available path lengths proportionally to each disconnected segment and weighted selection of RPs.The numbers of nodes distributed in disconnected segments are different. If a small number of RPs is selected in a segment with many nodes, then some of the nodes need to send the data to the RPs by long-distance multihop transmission, which goes against the principle of extending the network life because of increasing the energy consumption of the network. To set up more RPs in the segments with many nodes is a reasonable program; therefore, the available remaining path length will be allocated by the number of nodes in the segment. For example, the current path length of the mobile sink isL, and the total path length is limited to Llimit, and then, the available remaining path length of segment iis determined by
(3)Li=SizeVi∑k=1NSizeVk×Llimit−L,where function Size· can get the number of elements in a set and Vi is the set of sensor nodes distributed in segment i.As described in the system model, each node knows its own position. Nodes’x coordinates are X1,X2,⋯,XN, and their y coordinates are Y1,Y2,⋯,YN, respectively. Then, the distribution boundaries of the nodes are within a “detection rectangle,” where the bottom left corner of the rectangle is located at (minX1,X2,⋯,XN, minY1,Y2,⋯,YN) and the upper right corner of the rectangle is located at (maxX1,X2,⋯,XN, maxY1,Y2,⋯,YN). We divide the rectangle into α2 cells, with α to represent the granularity of the division. Put it another way, the rectangle is divided into α parts both vertically and horizontally. Next, for each segment, the weight of the nodes will be calculated according to formula (4), and the nodes will be sorted in descending order of weight. In each round, a new RPs will be added in order. If the new RPs does not cause the path length to exceed the limit, it will be retained. The factor β in formula (4) indicates the number of nodes in the cell to which the node belongs and reflects the density of the nodes. On the other hand, it is not appropriate for a large number of RPs to come together; new RPs should have some distance from the existing RPs; therefore, the factor φ is proportional to the number of RPs that already exist in the cell to which the node belongs.
(4)W=β−φ.Finally, we acquire the final RPs set and the corresponding mobile sink’s travelling path by the algorithm described in Algorithm3. The segments with more nodes will set up more RPs. The selection of the RPs strategy includes the consideration of segment size, shape, and distribution of nodes, which is conducive to reducing network energy consumption and extend the network life.


## 4. Performance Evaluation

The experiment has been implemented in a Java program. Experiments are conducted on a desktop with an Intel i3-4170 processor at 3.7GHz, 8GB memory, and a 64-bit Windows 10 operation system. The simulations are conducted in 1000× 1000 m2 fields wherein random topologies are generated for a varying number of segments. Sensor nodes have a communication range fixed at 30 m, which are deployed in segments randomly. The segment topologies are ever-changing; in order to measure the size of the area and the difference in shape, the standard deviation σ is defined in formula (5), where the factor σ reflects the difference in shape and size between segments. For a segment, its corresponding δ is given by formula (6); the segment is regarded as a quality uniform pattern; and its centroid can be found.S is the area of the segment, and Scircle is the area of a circle, where the center of this circle is located in the segment’s centroid and has an area equal to that segment. μ is given by formula (7), which represents the average of δ.
(5)σ=1N∑i=1Nδi−μ2,(6)δ=SScircle,(7)μ=1N∑i=1Nδi.We let each segment to be a circle with a radius of 40 m or 50 m, which means thatS=800 or S=500. Figure 7 shows the shortest mobile sink’s travelling path length required to connect all segments, where the number of segments is varying from 10 to 60. From the figure, we can see that our approach outperforms DGM-RPS algorithm with about 20% less path length on average, because the DGM-RPS algorithm builds the geometry tree and does not take full account of the shape and size of each segment, and the RPs selection is always based on the product of distance and transmission hop count. In the case of significant differences between segments, DGM-RPS has a lower priority for setting RPs in areas with smaller area and fewer nodes, which may result in using a fairly long path to access all segments. As the standard deviation σ increases, the advantages of our approach will become increasingly apparent; this indicates that our approach is more suitable for the case of large differences between segments.Figure 7
Total path length to visit all segments.
(a)
S=800 andσ=20(b)
S=500 and σ=20We changed the shape and size of each segment while maintaining the value ofμ constant, so that each topology corresponds to σ. We set the number of segments to 20, which are randomly generated and satisfy the constraints that S=800. Figure 8 shows that when the differences between segments increased, our program performed better. With the increase of σ, the path length required for the DGM-RPS method and PM-LPDR remains essentially unchanged, while the length of visit all segments of our approach is showing a downward trend. Because we fixed μ, a larger value of σ means the area of some segments is relatively large or the shape of the segment is like a long strip, which caused the first RPs to be selected near the boundary of the segment and closer to the center point. Our approach takes full advantage of the shape of the segment, so as to achieve the effect of shortening the path.Figure 8
Total path length to visit several segments withS=800.
(a)
Visit 20 segments(b)
Visit 40 segmentsThe energy consumption of a sensor includes the power for sensing, receiving, and transmission. In this paper, we only take the energy consumption of receiving and transmission into account since the energy consumption for sensing is negligible compared with the other two types of energy consumption. Sensor nodes deployed in different segments cannot communicate with each other by multihop transmission. The energy consumption of a node to transmitk bits data over distance d is shown as
(8)ETxk,d=k×Eelec+k×εfs×d2d<d0k×Eelec+k×εmp×d4d≥d0.where Eelec=50nJ/bit, εfs=10pJ/bit/m2, d0=87m, and εmp=0.0013pJ/bit/m4.In the case of total length of the mobile sink’s path, travelling length cannot exceed 3400 m or 5000 m, and the detection rectangle is divided into 20 × 20 cells, whileS was set to 500 andσ was set to 20. We consider the network consists of 20 segments, while the number of nodes from 100 to 800 and all nodes generate 1bit data every round. The performances of three methods are shown in Figure 9. Compared to other methods, our solution can save more than 10% of the energy for the network, thanks to the full consideration of the distribution density of nodes, while the design of the attenuation factor to the distance between RPs is too close. Let the total length constraint of the path remains unchanged, while μ=40 and σ=20. Under these circumstances, using DGM-RPS algorithm and our approach to obtain the position of RPs and the corresponding path are shown in Figure 9(a) and Figure 9(b), respectively.Figure 9
Network energy consumption of three methods with 20 segments andS=500, σ=20.
(a)
Llimit=5000m(b)
Llimit=3400m


## 5. Conclusion

In this paper, we propose an efficient data gathering mechanism for disconnected wireless sensor networks with a mobile sink. The mobile sink traverses the entire network and stops only at the rendezvous points (RPs) while gathers the data from sensors in every disconnected segment. We measure the shape of disconnected segments, layering them by use of the convex hull, and then design the travelling path of the mobile sink to minimize the travel latency to visit all disconnected segments. At least one RPs will be selected in a segment firstly, and then, on this basic, we consider the distribution density of sensor nodes and the location of the RPs already exist to adding new RPs, which make good use of the margin to reducing the energy consumption and prolong the lifetime of network. We carry out some simulations, which reflect the advantages of our strategy in terms of path length and network lifetime.



---

*Source: 4763153-2022-04-14.xml*