# Multiwinner Voting for Energy-Efficient Mobile Sink Rendezvous Selection in Wireless Sensor Network

Authors: Xiaofeng Wu; Zhuangqi Chen; Yi Zhong; Hui Zhu; Xiao Chen; Pingjian Zhang
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Recent studies have demonstrated the advantage of applying mobile sink to prevent the energy-hole problem and prolong network lifetime in wireless sensor network. However, most researches treat the touring length constraint simply as the termination indicator of rendezvous point selection, which leads to a suboptimal solution. In this paper, we notice that the optimal set of rendezvous points is unknown but deterministic and propose to elect the set of rendezvous points directly with the multiwinner voting-based method instead of step-by-step selection. A weighted heuristic voter generation method is introduced to choose the representative voters, and a scoring rule is also well designed to obtain a satisfying solution. We also employ an iterative schema for the voting score update to refine the solution. We have conducted extensive experiments, and the results show that the proposed method can effectively prolong the network lifetime and achieve the competitive performance with other SOTA methods. Compared to the methods based on step-by-step selection, the proposed method increases the network lifetime by 23.2% and 10.5% on average under the balanced-distribution and unbalanced-distribution scenarios, respectively.


---

## Body

## 1. Introduction

In recent years, wireless sensor network (WSN) has been widely deployed in numerous applications, such as smart agriculture [1, 2], military [3], healthcare [4, 5], smart surveillance [6], and home monitoring [7]. A WSN consists of several sensor nodes, which are randomly distributed in the monitoring filed. The sensors are responsible for sensing, processing, and transmitting data, and all operations will consume some energy. In most applications, the sensor nodes are powered by the battery and deployed in unattended or harsh environment, which makes the battery replacement be difficult or even impossible. In addition, the network does not work if some sensor fails.To prolong the network lifetime, several energy-efficient data collection algorithms have been proposed. In conventional data collection methods, all sensor nodes are static, and the sensed data is transmitted to the sink through multihop [8, 9]. This strategy leads to an energy-hole problem, where the nodes near the sink will have a greater traffic load and deplete energy prematurely. To alleviate the unbalanced energy consumption, some data collection algorithms [10] have employed the mobile sink (MS) to collect data, where the MS starts from the base station (BS), visits sensor nodes, aggregates data, and returns to BS. Since sensor nodes transmit data directly to the MS, the energy can be saved to the maximum. However, when the scale of WSN becomes larger, the traveling path will become longer and the delay of data collection will also be higher which is unacceptable. An intuitive solution is introducing multiple mobile sinks and each responsible for a different area [11–13]. However, the MS is usually expensive, and a high delay is inevitable for the sensor node deployed in a large distance, which makes the solution impractical. Another solution is to combine the MS with multihop route, where data collection is hierarchical [14–16]. All sensor nodes are first clustered into several groups, and a rendezvous point is selected in each group, which buffers data sensed by the sensor nodes in the same group. The MS is then used to visit the rendezvous points and aggregate data. The touring length of MS is usually limited by a delay constraint. Most existing methods select the candidate rendezvous based on some greedy rule or in heuristic manner, and the selection procedure is terminated when the touring path is longer than the maximum length Lmax. The touring length constraint is not well combined into the procedure of rendezvous selection, which significantly limits the upper bound of performance.In this paper, we investigate whether we can combine the delay constraint into the rendezvous selection procedure instead of treating the constraint simply as a termination condition. A feasible solution can be viewed as a subset of sensor nodes. Given a specific configuration of WSN, we notice that the optimal solution is unknown but deterministic. Based on this fact, the problem of data collection can be turned into electing directly an optimal subset of sensor nodes (i.e., the optimal set of rendezvous points) as the solution, and thus, the delay constraint will be implicitly considered. To this end, we proposed a multiwinner voting- (MV-) [17, 18] based algorithm for energy-efficient rendezvous selection. The multiwinner voting is aimed at electing multiple satisfying winners (i.e., optimal rendezvous points) from given candidates (i.e., all sensor nodes). We treat feasible solution as the “voter,” and the “voter” with better performance would have higher weight for selecting winners. Each “voter” would favor the candidate sensors in the corresponding solution, and the candidates with the highest score would be chosen as the winners. We first generate several representative “voters” and then assign a score for each sensor node with the “voters.” Furthermore, the scores are updated to refine the final solution in an iterative strategy. The following summarizes our main contributions:
(i)
We formulated the data collection problem as the selection of optimal rendezvous points and proposed an MV-based algorithm to directly elect the set of rendezvous points, which alleviates the suboptimality caused by without considering delay constraint during rendezvous selection(ii)
We proposed a simple but efficient weighted heuristic method for “voter” generation and a practicable scoring rule for getting a satisfying solution(iii)
We employed an iterative schema for the update of voting scores, and the voting result will coverage to the optimal solution with maximum network lifetimeThe rest of this paper is organized as follows: we review the related works in Section2, formulate the problem in Section 3, detail the proposed MV-based rendezvous selection algorithm in Section 4, analyse the experimental results in Section 5, and conclude this paper in Section 6.


## 2. Related Works

The issue of rendezvous selection has been widely studied in recent literature. As shown in Table1, the proposed methods can be mainly classified into three categories: cluster-based, tree-based, and grid-based. We briefly review those approaches in the following.Table 1
Overview of the rendezvous selection methods.
CategoriesBasic stepsReferencesCluster-based(1) Perform clustering to generate several groups(2) Select a cluster head as the rendezvous point in each group[19, 20]Tree-based(1) Construct a routing tree(2) Split it into several subtrees(3) Treat the root of each subtree as the rendezvous points[21–24]Grid-based(1) Split monitoring region into several grids(2) Elect a rendezvous point in each grid[25–27]


### 2.1. Cluster-Based

In the cluster-based methods, several cluster heads are first selected as the rendezvous points, and each sensor node transmits data to the closest rendezvous points. The authors in [19] proposed a dynamic clustering approach, where the cluster heads are first selected based on the threshold value computed by three different parameters and the ant colony optimization (ACO) algorithm is then employed to find the shortest path to visit all cluster heads. The procedure is repeated in each round, and the cluster heads will be reselected to alleviate premature death. In [20], the hierarchical agglomerative clustering (HAC) is used to perform clustering, where each node is treated as a cluster and merged successively based on single linkage which considers the smallest distance between any two sensor nodes from different clusters. The number of clusters is determined based on the average compact-separate proportion, and the centroid of each cluster is selected as the rendezvous points.


#### 2.1.1. Tree-Based

In the tree-based methods, the WSN is organized as several trees, where the root nodes of trees are denoted as the rendezvous points and responsible for buffering data from the nodes in the same tree. [21] introduced a weight-based tree construction first to construct a tree, in which it considers the residual energy, local node density, and the distance to the base station. Then, a tree decomposition algorithm is performed to select suitable nodes as subrendezvous points, which takes the number of hop to the root and the number of child nodes into account. The methods in [23, 24] first construct a routing tree using the Prim algorithm to minimize the overall distance of route and then assign a weight to each node with considering the possible energy saving. In each iteration, the node with highest weight will be selected as the rendezvous point, and weights of nodes should be updated. The authors in [22] designed multilevel routing framework with dynamic spanning tree to balance the network load and prolong the network lifetime, where some nodes are selected as the rendezvous points based on the motion of mobile sink.


#### 2.1.2. Grid-Based

In the grid-based methods, the monitoring field is first partitioned into several grids and the cluster heads are elected in each grids. In [25], the entire network area is first divided into two-dimensional logical grids with fixed cell length, and then, the node closest to the center of each grid is selected as the rendezvous. In [26], the residual energy of nodes is also considered when selecting the cluster head in each grid and the rendezvous point is reselected when the node’s energy is less than the threshold value. Unlike other grid-based methods where the mobile sink has to visit each grid, the authors in [27] devised a novel virtual grid-based method where only one-ninth of grids should be visited. After dividing the monitoring area into small grids, several grid cells are selected as the visiting points. The mobile sink will receive data from adjacent grid heads through single hop when it locates in a visiting point.


## 2.1. Cluster-Based

In the cluster-based methods, several cluster heads are first selected as the rendezvous points, and each sensor node transmits data to the closest rendezvous points. The authors in [19] proposed a dynamic clustering approach, where the cluster heads are first selected based on the threshold value computed by three different parameters and the ant colony optimization (ACO) algorithm is then employed to find the shortest path to visit all cluster heads. The procedure is repeated in each round, and the cluster heads will be reselected to alleviate premature death. In [20], the hierarchical agglomerative clustering (HAC) is used to perform clustering, where each node is treated as a cluster and merged successively based on single linkage which considers the smallest distance between any two sensor nodes from different clusters. The number of clusters is determined based on the average compact-separate proportion, and the centroid of each cluster is selected as the rendezvous points.


### 2.1.1. Tree-Based

In the tree-based methods, the WSN is organized as several trees, where the root nodes of trees are denoted as the rendezvous points and responsible for buffering data from the nodes in the same tree. [21] introduced a weight-based tree construction first to construct a tree, in which it considers the residual energy, local node density, and the distance to the base station. Then, a tree decomposition algorithm is performed to select suitable nodes as subrendezvous points, which takes the number of hop to the root and the number of child nodes into account. The methods in [23, 24] first construct a routing tree using the Prim algorithm to minimize the overall distance of route and then assign a weight to each node with considering the possible energy saving. In each iteration, the node with highest weight will be selected as the rendezvous point, and weights of nodes should be updated. The authors in [22] designed multilevel routing framework with dynamic spanning tree to balance the network load and prolong the network lifetime, where some nodes are selected as the rendezvous points based on the motion of mobile sink.


### 2.1.2. Grid-Based

In the grid-based methods, the monitoring field is first partitioned into several grids and the cluster heads are elected in each grids. In [25], the entire network area is first divided into two-dimensional logical grids with fixed cell length, and then, the node closest to the center of each grid is selected as the rendezvous. In [26], the residual energy of nodes is also considered when selecting the cluster head in each grid and the rendezvous point is reselected when the node’s energy is less than the threshold value. Unlike other grid-based methods where the mobile sink has to visit each grid, the authors in [27] devised a novel virtual grid-based method where only one-ninth of grids should be visited. After dividing the monitoring area into small grids, several grid cells are selected as the visiting points. The mobile sink will receive data from adjacent grid heads through single hop when it locates in a visiting point.


## 2.1.1. Tree-Based

In the tree-based methods, the WSN is organized as several trees, where the root nodes of trees are denoted as the rendezvous points and responsible for buffering data from the nodes in the same tree. [21] introduced a weight-based tree construction first to construct a tree, in which it considers the residual energy, local node density, and the distance to the base station. Then, a tree decomposition algorithm is performed to select suitable nodes as subrendezvous points, which takes the number of hop to the root and the number of child nodes into account. The methods in [23, 24] first construct a routing tree using the Prim algorithm to minimize the overall distance of route and then assign a weight to each node with considering the possible energy saving. In each iteration, the node with highest weight will be selected as the rendezvous point, and weights of nodes should be updated. The authors in [22] designed multilevel routing framework with dynamic spanning tree to balance the network load and prolong the network lifetime, where some nodes are selected as the rendezvous points based on the motion of mobile sink.


## 2.1.2. Grid-Based

In the grid-based methods, the monitoring field is first partitioned into several grids and the cluster heads are elected in each grids. In [25], the entire network area is first divided into two-dimensional logical grids with fixed cell length, and then, the node closest to the center of each grid is selected as the rendezvous. In [26], the residual energy of nodes is also considered when selecting the cluster head in each grid and the rendezvous point is reselected when the node’s energy is less than the threshold value. Unlike other grid-based methods where the mobile sink has to visit each grid, the authors in [27] devised a novel virtual grid-based method where only one-ninth of grids should be visited. After dividing the monitoring area into small grids, several grid cells are selected as the visiting points. The mobile sink will receive data from adjacent grid heads through single hop when it locates in a visiting point.


## 3. Problem Formulation

In this paper, we consider a wireless sensor network (WSN) with one mobile sink (MS). Several sensor nodes (SNs) are randomly distributed in a surveillance area and sense the circumstance. Some of them are selected as the rendezvous points and responsible for collecting data generated by partial SNs. A mobile sink is employed to periodically visit RPs and aggregates data sensed by all SNs. Each SN receives, transmits, and processes data packet with energy consuming. A WSN’s lifetime is dependent on the SN, which uses up energy first.


### 3.1. Assumptions

Before formulating the problem, we make several assumptions in this paper:(i)
All SNs are homogeneous, stationary, and battery-powered with limited energy(ii)
SNs have a fixed communication range. Each SN can communicate (i.e., transmit and receive data) obstruction-free with other SNs located in its communication range(iii)
The energy consumption is mainly caused by transmitting and receiving data packets, while the partial one for processing data is negligible(iv)
Each SN generates one data packet withb bits in a round, where the term “round” denotes MS starts from the BS, traverses all rendezvous points, collects all data, and then returns to the BS(v)
All sensor nodes have enough capacity to buffer data packets(vi)
The MS moves periodically around the monitoring area with a fixed velocity and aggregates data from rendezvous points. The data must be sent to the BS at a desired time(vii)
The communication time between MS and rendezvous points can be ignored, as compared with the touring time of MS


### 3.2. Energy-Efficient Rendezvous Selection

A WSN can be modeled as a undirected graphG=V,E, where V=v0,v1,⋯,vn and E are the set of SNs and the set of edges between SNs in V, respectively. The v0 represents the base station, vi,i=1,⋯,n denotes sensor i, and n is the number of SNs. vi,vj∈E only if sensor i is located in the communication range of sensor j and vice versa. The initial energy of each sensor node is E0, and the energy consumptions for transmitting and receiving one data packet are Et and Er, respectively. In each round, sensor nodes transfer sensed data to their closest rendezvous point through either single hop or multihop. To this end, several nodes take the role of relay nodes, and the sensor i will receive NDi data packets and transmit NDi+1 data packets, where NDi corresponds to the number of child nodes of sensor i in the routing tree. Therefore, the energy consumption of sensor i can be formulated as
(1)Ei=NDi×Er+NDi+1×Et.Then, the lifetime of sensori is
(2)LTi=E0Ei.Since the network lifetime depends on the sensor depletes energy first, the network lifetime can be calculated as(3)LT=maxj∈VLTj.Furthermore, the rendezvous points should buffer all data sensed by the whole WSN and thus consume more energy than other sensors. It means that the network lifetimeLT is mainly affected by the rendezvous points, which can be reformulated as
(4)LT=maxj∈MLTj,where M denotes the set of rendezvous points.The main goal of devising a WSN is to maximize its network lifetime under the delay constraint:(5)Lv≤tmax,where tmax is the maximum acceptable delay of network and L and v are the touring length and touring velocity of MS, respectively. As the values of v and tmax are fixed, Equation (5) can be reformulated as
(6)L≤Lmax,where Lmax denotes the maximum allowed touring length for MS.To this end, a set of rendezvous pointsM=m0,m1,⋯,mp should be carefully selected. After the set of rendezvous points has been selected, an optimal touring path is also implicitly determined. Let Tour=m0′=m0,m1′,m2′,⋯,mp+1′=m0 be the optimal touring path. Then, the objective of well-designed WSN can be formulated as an optimal problem
(7)Maximizemaxj∈MLTj,s.t.∑i=0pdistmi′,mi+1′≤Lmax,where distmi′,mi+1′ is the Euclidean distance.


## 3.1. Assumptions

Before formulating the problem, we make several assumptions in this paper:(i)
All SNs are homogeneous, stationary, and battery-powered with limited energy(ii)
SNs have a fixed communication range. Each SN can communicate (i.e., transmit and receive data) obstruction-free with other SNs located in its communication range(iii)
The energy consumption is mainly caused by transmitting and receiving data packets, while the partial one for processing data is negligible(iv)
Each SN generates one data packet withb bits in a round, where the term “round” denotes MS starts from the BS, traverses all rendezvous points, collects all data, and then returns to the BS(v)
All sensor nodes have enough capacity to buffer data packets(vi)
The MS moves periodically around the monitoring area with a fixed velocity and aggregates data from rendezvous points. The data must be sent to the BS at a desired time(vii)
The communication time between MS and rendezvous points can be ignored, as compared with the touring time of MS


## 3.2. Energy-Efficient Rendezvous Selection

A WSN can be modeled as a undirected graphG=V,E, where V=v0,v1,⋯,vn and E are the set of SNs and the set of edges between SNs in V, respectively. The v0 represents the base station, vi,i=1,⋯,n denotes sensor i, and n is the number of SNs. vi,vj∈E only if sensor i is located in the communication range of sensor j and vice versa. The initial energy of each sensor node is E0, and the energy consumptions for transmitting and receiving one data packet are Et and Er, respectively. In each round, sensor nodes transfer sensed data to their closest rendezvous point through either single hop or multihop. To this end, several nodes take the role of relay nodes, and the sensor i will receive NDi data packets and transmit NDi+1 data packets, where NDi corresponds to the number of child nodes of sensor i in the routing tree. Therefore, the energy consumption of sensor i can be formulated as
(1)Ei=NDi×Er+NDi+1×Et.Then, the lifetime of sensori is
(2)LTi=E0Ei.Since the network lifetime depends on the sensor depletes energy first, the network lifetime can be calculated as(3)LT=maxj∈VLTj.Furthermore, the rendezvous points should buffer all data sensed by the whole WSN and thus consume more energy than other sensors. It means that the network lifetimeLT is mainly affected by the rendezvous points, which can be reformulated as
(4)LT=maxj∈MLTj,where M denotes the set of rendezvous points.The main goal of devising a WSN is to maximize its network lifetime under the delay constraint:(5)Lv≤tmax,where tmax is the maximum acceptable delay of network and L and v are the touring length and touring velocity of MS, respectively. As the values of v and tmax are fixed, Equation (5) can be reformulated as
(6)L≤Lmax,where Lmax denotes the maximum allowed touring length for MS.To this end, a set of rendezvous pointsM=m0,m1,⋯,mp should be carefully selected. After the set of rendezvous points has been selected, an optimal touring path is also implicitly determined. Let Tour=m0′=m0,m1′,m2′,⋯,mp+1′=m0 be the optimal touring path. Then, the objective of well-designed WSN can be formulated as an optimal problem
(7)Maximizemaxj∈MLTj,s.t.∑i=0pdistmi′,mi+1′≤Lmax,where distmi′,mi+1′ is the Euclidean distance.


## 4. The Proposed MV Algorithm

### 4.1. Overview

Algorithm 1: MV-based rendezvous selection algorithm.
Input: routing tree T, the number of top voters Ntop.Output: a set of trees Trps rooted by rendezvous points1: initialize weightsW;2:Tbest⟵;3:forepoch=0⟶MAXIterationdo4:  samplen′ voters from the MPD defined in W;5:Tall⟵;6:for all voters do7:M′=m1,m2,⋯,mp′⟵ current voter;8:T′⟵ deep copy T;9:form′ in M′do10:     break the edge between nodem′ and its parent in T′;11:end for12:Tall⟵Tall∪T′;13:end for14:  sortT′∈Tall based on the maxi∈T′NDi in descending order;15:Ttop⟵ the first Ntop-th T′ in the ordered Tall;16:forT′ in Ttopdo17:   evaluate scoreS=s0,s1,⋯,sn according to Equation (8);18:W=W+S;19:end for20:Tbest⟵Tbest∪Ttop;21:end for22:Trps⟵argminT′∈TbestmaxndT′;23:returnTrps;In this paper, we propose to model the rendezvous selection problem in terms of multiwinner voting (MV), where the rendezvous points are elected by the poll of some representative voters. The motivation is based on the truth that the optimal set of rendezvous is unknown but certain. Selecting the optimal rendezvous can be viewed as electing several suitable sensors (or called “multiwinner”) from all SNs. As shown in Figure1, the proposed MV-based rendezvous selection algorithm contains four stages: routing tree construction, rendezvous selection, traveling path planning, and virtual rendezvous point marking. We detail each stage in the following sections and then give the complexity analysis of the proposed algorithm.Figure 1
The proposed multiwinner voting-based rendezvous selection algorithm, which contains four stages: routing tree construction, rendezvous selection, traveling path planning, and virtual rendezvous point marking.


### 4.2. Routing Tree Construction

To minimize the overall communication cost between sensors, a minimum spanning tree- (MST-) based routing tree (also known as “data forwarding tree”) is first constructed using the Prim algorithm. The routing tree is employed to forward data, which is rooted by the base station and contains all SNs. When the sensori is chosen as the rendezvous, the edge between sensor i and its parent node would be broken. Each sensor receives data from its child nodes and transmits data to its parent. Specially, the rendezvous points transmit data directly to MS when MS reaches the position rendezvous located.


### 4.3. MV-Based Rendezvous Selection

Based on the constructed routing tree, a multiwinner voting- (MV-) based algorithm is introduced for rendezvous selection. An MV generally consists of three main components: candidate, voter, and scoring rule. The candidates are undoubtedly all SNs in the rendezvous selection problem. To reach a satisfying result, the key is how to devise the voter and scoring rule. In this paper, we consider the “voter” as a feasible solution, which contains a set of SNs. Given a “voter”M=m1,m2,⋯,mp, the scoring rule is defined as follows:
(8)fv,M=11+maxmi∈MNDmi,v∈M,0,otherwise,where v denotes a candidate and the NDmi is the number of child nodes of sensor node mi in the routing tree, which is at least 0. Intuitively, a candidate will get a higher score if it is in a solution M which has a smaller value of maxmi∈MNDmi. In addition, from Equations (1), (2), and (4), one can find that the network lifetime LT is inversely proportional to the term maxmi∈MNDmi. That is, a candidate will score high if it is in the solution with longer network lifetime. Furthermore, a candidate will also win a high mark if most “voters” vote for it. Having the support of majority of “voters” means the candidate is critical to constructing a feasible solution. In summary, based on the above design, a candidate rendezvous will have a higher score if it is in a better solution after voting.To this end, the question is how to generate the “voter.” Motivated by most heuristic algorithms, we proposed a weight-based selection method for voter generation. Initially, all the SNs (or called “candidates”) are weighted withW=w0,w1,⋯,wn. We sample n′ candidates orderly from the multinomial probability distribution (MPD) defined in the weight W. It is worth noting that the sum of the weights does not need to be one, and the higher weight denotes a higher probability. Then, we chose the first p candidates as a “voter,” where p is the maximum number meeting the touring length constraint. Several “voters” can be generated by repeating above steps.However, there was a conflict between the weightW and multiwinner voting. The W is a component in the MV and defines the probability of being rendezvous of SNs, while the MV is employed to generate the probability for each SN. To alleviate the “deadlock,” we proposed an iterative MV-based algorithm for rendezvous selection. We treat the weight W as the voting result and perform voting and update iteratively. The voting step generates several “voter” based on the weight W and scores each candidate using the scoring rule defined in Equation (8), and the update step updates the weight W using the result of voting. The proposed rendezvous selection method is detailed in Algorithm 1. To accelerate convergence, we initialize the weight W based on the result of a greedy algorithm, where a candidate will get higher weight if it is in the result. In addition, we also consider filtering the “voters,” in which only the k-th best “voters” are used.


### 4.4. Touring Path Planning

Algorithm 2: Touring path planning.
Input: a set of rendezvous points M=m0,m1,m2,⋯,mpOutput:Tour=m0′=v0,m1′,m2′,⋯,mp′,mp+1′=v0 the visiting path1: construct a minimum polygonTour=v0′,v1′,⋯,vm′ bounding all rendezvous points;2:P⟵v′v′∈Tour;3:S⟵M−P;4:forv in Sdo5:  /∗d·,· denotes the Euclidean distance. ∗/6:i⟵argmin0≤i≤Pdv,vi′+dv,vi+1′−dvi′,vi+1′;7:  insert nodev into the position between vi′,vi+1′;8:P⟵P∪v;9:S⟵S−v;10:end for11: move base stationv0 to the first position in Tour by circle shifting;12:returnTour;After the sets of rendezvous points are selected, the touring path should be planned for MS to visit all rendezvous points. However, the path planning problems have been proven to be an NP-hard problem, which can be formulated as the traveling salesman problem (TSP). In this paper, we employ a geometric path construction algorithm (GPCA) [23, 28] to solve the path planning. Given a set of rendezvous points, the GPCA first constructs a polygon with minimum perimeter to surround all rendezvous points, where the polygon’s vertices are the subset of rendezvous points. Then, the points inside the polygon join the polygon orderly in a greedy manner. The detail of the touring path planning is described in the Algorithm 2.


### 4.5. Virtual Rendezvous Points

Algorithm 3: Virtual rendezvous point recognition.
Input: the visiting path Tour , all sensor nodes V, the communication range rOutput: a set of virtual rendezvous points VRPs1:VRPs⟵2:forv in Vdo3:  ifv is rendezvous points then4:   continue;5:end if6:fori=1 to Tourdo7:vj,vk⟵Touri−1,Touri;8:    evaluate the distanced between node v and edge vj,vk;9:ifd≤rthen10:VRPs⟵VRPs∪v;11:     break;12:end if13:end for14:end for15:returnVRPs;To further prolong the network lifetime, the virtual rendezvous points (VRPs) are introduced. The VRP is the nonrendezvous sensor and can directly send data to MS when the MS is located in its communication range. Algorithm3 details the recognition of VRPs. When a sensor is marked as a VRP, the edge between the sensor and its parent is broken in the routing tree. Figure 2 illustrates an example of the recognition of VRPs, where the red lines denote the touring path and the nodes in green color are marked as the VRPs.Figure 2
An example of virtual rendezvous point recognition. The red points and lines denote the rendezvous points and touring paths, respectively. The virtual rendezvous points (in green color) are determined based on the distance between the nodes and the touring paths.


### 4.6. Complexity Analysis

In routing tree construction phase, the time complexity isOn2 with Prim algorithm, where n is the number of sensor nodes. In rendezvous selection phase described in Algorithm 1, the complexity of step 1 with a greedy algorithm is On2, the complexity of steps 7-12 is Om3, where m denotes the number of rendezvous points, and the complexity of steps 14-20 is Om2. In this case, given t iterations and k voters, the complexity of Algorithm 1 is On2+t×k×m3+m2=On2+tkm3. The complexities of Algorithm 2 and Algorithm 3 are Om2 and Omn, respectively. Since the number of rendezvous points m is less than the number of sensor nodes n, the overall time complexity is On2+On2+tkm3+Om2+Omn=On2+tkm3.


## 4.1. Overview

Algorithm 1: MV-based rendezvous selection algorithm.
Input: routing tree T, the number of top voters Ntop.Output: a set of trees Trps rooted by rendezvous points1: initialize weightsW;2:Tbest⟵;3:forepoch=0⟶MAXIterationdo4:  samplen′ voters from the MPD defined in W;5:Tall⟵;6:for all voters do7:M′=m1,m2,⋯,mp′⟵ current voter;8:T′⟵ deep copy T;9:form′ in M′do10:     break the edge between nodem′ and its parent in T′;11:end for12:Tall⟵Tall∪T′;13:end for14:  sortT′∈Tall based on the maxi∈T′NDi in descending order;15:Ttop⟵ the first Ntop-th T′ in the ordered Tall;16:forT′ in Ttopdo17:   evaluate scoreS=s0,s1,⋯,sn according to Equation (8);18:W=W+S;19:end for20:Tbest⟵Tbest∪Ttop;21:end for22:Trps⟵argminT′∈TbestmaxndT′;23:returnTrps;In this paper, we propose to model the rendezvous selection problem in terms of multiwinner voting (MV), where the rendezvous points are elected by the poll of some representative voters. The motivation is based on the truth that the optimal set of rendezvous is unknown but certain. Selecting the optimal rendezvous can be viewed as electing several suitable sensors (or called “multiwinner”) from all SNs. As shown in Figure1, the proposed MV-based rendezvous selection algorithm contains four stages: routing tree construction, rendezvous selection, traveling path planning, and virtual rendezvous point marking. We detail each stage in the following sections and then give the complexity analysis of the proposed algorithm.Figure 1
The proposed multiwinner voting-based rendezvous selection algorithm, which contains four stages: routing tree construction, rendezvous selection, traveling path planning, and virtual rendezvous point marking.


## 4.2. Routing Tree Construction

To minimize the overall communication cost between sensors, a minimum spanning tree- (MST-) based routing tree (also known as “data forwarding tree”) is first constructed using the Prim algorithm. The routing tree is employed to forward data, which is rooted by the base station and contains all SNs. When the sensori is chosen as the rendezvous, the edge between sensor i and its parent node would be broken. Each sensor receives data from its child nodes and transmits data to its parent. Specially, the rendezvous points transmit data directly to MS when MS reaches the position rendezvous located.


## 4.3. MV-Based Rendezvous Selection

Based on the constructed routing tree, a multiwinner voting- (MV-) based algorithm is introduced for rendezvous selection. An MV generally consists of three main components: candidate, voter, and scoring rule. The candidates are undoubtedly all SNs in the rendezvous selection problem. To reach a satisfying result, the key is how to devise the voter and scoring rule. In this paper, we consider the “voter” as a feasible solution, which contains a set of SNs. Given a “voter”M=m1,m2,⋯,mp, the scoring rule is defined as follows:
(8)fv,M=11+maxmi∈MNDmi,v∈M,0,otherwise,where v denotes a candidate and the NDmi is the number of child nodes of sensor node mi in the routing tree, which is at least 0. Intuitively, a candidate will get a higher score if it is in a solution M which has a smaller value of maxmi∈MNDmi. In addition, from Equations (1), (2), and (4), one can find that the network lifetime LT is inversely proportional to the term maxmi∈MNDmi. That is, a candidate will score high if it is in the solution with longer network lifetime. Furthermore, a candidate will also win a high mark if most “voters” vote for it. Having the support of majority of “voters” means the candidate is critical to constructing a feasible solution. In summary, based on the above design, a candidate rendezvous will have a higher score if it is in a better solution after voting.To this end, the question is how to generate the “voter.” Motivated by most heuristic algorithms, we proposed a weight-based selection method for voter generation. Initially, all the SNs (or called “candidates”) are weighted withW=w0,w1,⋯,wn. We sample n′ candidates orderly from the multinomial probability distribution (MPD) defined in the weight W. It is worth noting that the sum of the weights does not need to be one, and the higher weight denotes a higher probability. Then, we chose the first p candidates as a “voter,” where p is the maximum number meeting the touring length constraint. Several “voters” can be generated by repeating above steps.However, there was a conflict between the weightW and multiwinner voting. The W is a component in the MV and defines the probability of being rendezvous of SNs, while the MV is employed to generate the probability for each SN. To alleviate the “deadlock,” we proposed an iterative MV-based algorithm for rendezvous selection. We treat the weight W as the voting result and perform voting and update iteratively. The voting step generates several “voter” based on the weight W and scores each candidate using the scoring rule defined in Equation (8), and the update step updates the weight W using the result of voting. The proposed rendezvous selection method is detailed in Algorithm 1. To accelerate convergence, we initialize the weight W based on the result of a greedy algorithm, where a candidate will get higher weight if it is in the result. In addition, we also consider filtering the “voters,” in which only the k-th best “voters” are used.


## 4.4. Touring Path Planning

Algorithm 2: Touring path planning.
Input: a set of rendezvous points M=m0,m1,m2,⋯,mpOutput:Tour=m0′=v0,m1′,m2′,⋯,mp′,mp+1′=v0 the visiting path1: construct a minimum polygonTour=v0′,v1′,⋯,vm′ bounding all rendezvous points;2:P⟵v′v′∈Tour;3:S⟵M−P;4:forv in Sdo5:  /∗d·,· denotes the Euclidean distance. ∗/6:i⟵argmin0≤i≤Pdv,vi′+dv,vi+1′−dvi′,vi+1′;7:  insert nodev into the position between vi′,vi+1′;8:P⟵P∪v;9:S⟵S−v;10:end for11: move base stationv0 to the first position in Tour by circle shifting;12:returnTour;After the sets of rendezvous points are selected, the touring path should be planned for MS to visit all rendezvous points. However, the path planning problems have been proven to be an NP-hard problem, which can be formulated as the traveling salesman problem (TSP). In this paper, we employ a geometric path construction algorithm (GPCA) [23, 28] to solve the path planning. Given a set of rendezvous points, the GPCA first constructs a polygon with minimum perimeter to surround all rendezvous points, where the polygon’s vertices are the subset of rendezvous points. Then, the points inside the polygon join the polygon orderly in a greedy manner. The detail of the touring path planning is described in the Algorithm 2.


## 4.5. Virtual Rendezvous Points

Algorithm 3: Virtual rendezvous point recognition.
Input: the visiting path Tour , all sensor nodes V, the communication range rOutput: a set of virtual rendezvous points VRPs1:VRPs⟵2:forv in Vdo3:  ifv is rendezvous points then4:   continue;5:end if6:fori=1 to Tourdo7:vj,vk⟵Touri−1,Touri;8:    evaluate the distanced between node v and edge vj,vk;9:ifd≤rthen10:VRPs⟵VRPs∪v;11:     break;12:end if13:end for14:end for15:returnVRPs;To further prolong the network lifetime, the virtual rendezvous points (VRPs) are introduced. The VRP is the nonrendezvous sensor and can directly send data to MS when the MS is located in its communication range. Algorithm3 details the recognition of VRPs. When a sensor is marked as a VRP, the edge between the sensor and its parent is broken in the routing tree. Figure 2 illustrates an example of the recognition of VRPs, where the red lines denote the touring path and the nodes in green color are marked as the VRPs.Figure 2
An example of virtual rendezvous point recognition. The red points and lines denote the rendezvous points and touring paths, respectively. The virtual rendezvous points (in green color) are determined based on the distance between the nodes and the touring paths.


## 4.6. Complexity Analysis

In routing tree construction phase, the time complexity isOn2 with Prim algorithm, where n is the number of sensor nodes. In rendezvous selection phase described in Algorithm 1, the complexity of step 1 with a greedy algorithm is On2, the complexity of steps 7-12 is Om3, where m denotes the number of rendezvous points, and the complexity of steps 14-20 is Om2. In this case, given t iterations and k voters, the complexity of Algorithm 1 is On2+t×k×m3+m2=On2+tkm3. The complexities of Algorithm 2 and Algorithm 3 are Om2 and Omn, respectively. Since the number of rendezvous points m is less than the number of sensor nodes n, the overall time complexity is On2+On2+tkm3+Om2+Omn=On2+tkm3.


## 5. Performance Evaluation

### 5.1. Experimental Setup

To benchmark our proposed algorithm, we have conducted extensive experiments using simulator written in Python. We consider a WSN with the monitoring field of size300×300 m2, where the sensor nodes are distributed randomly in the field and the number of sensors varies from 100 to 600. Two types of distribution are implemented:
(i)
Balanced distribution (BD): all the sensors are uniformly distributed in the monitoring filed(ii)
Unbalanced distribution (UD): the monitoring field is divided into3×3 squares, where each squares is 100×100 m2 in size. Five squares are chosen to deploy sensors randomly, where the squares do not share the edge with each otherIn addition, the communication range of sensors is set to 30 m, and the moving velocity of the mobile sink is 1 m/s. Each sensor can communicate with other sensors and MS, which are located in the communication range, through one hop. The initial energy of each sensor isEi=100 J, and the energy consumption for transmitting and receiving one data packet is Et=0.021 J and Er=0.015 J, respectively. The configuration of network is detailed in Table 2.Table 2
The configuration of network.
DescriptionValueSimulatorPythonNode deploymentRandomNetwork area300m×300m# of sensor nodes100-300Communication range30 mEt0.021 JEr0.015 JE0100 JVelocity of mobile sink1m/sTo validate the effectiveness of the proposed method, we compare it with other SOTA methods: dynamic directional routing (DDR) [29], weighted rendezvous planning (WRP) [24], energy-aware path construction (EAPC) [23], and end-to-end ant colony optimal- (ACO-) based rendezvous selection [30].
(i)
DDR is a novel routing protocol, which considers the mobility of sensor nodes. It is aimed at controlling the dataflow in the network to optimize the routes toward the sink. The DDR can effectively improve the network time and has the state-of-the-art performance under the scenario using static sink(ii)
WRP is an iterative greedy algorithm. At each iteration, each sensor is first weighted based on its hop distance to the closest rendezvous point and the number of nodes in the subtree rooted by the sensor. A sensor with maximum value of weight is selected as the rendezvous point. The iteration is terminated if the touring length exceeds the predefined maximum length(iii)
EAPC is similar to the WRP, which is a heuristic algorithm. It takes the Euclidean distance between sensor and its closest rendezvous point into consideration in addition. The EAPC algorithm reached an impressive performance with mobile sink(iv)
ACO is an end-to-end data collection strategy. It performs the rendezvous selection and touring planning simultaneously. The ACO algorithm provides a SOTA performance with a high computational complexityWe compare them without considering virtual rendezvous points for fairness. Several performance metrics, including network lifetime, total energy consumption, fairness index, efficient index, and running time, are used to comprehensively benchmark the proposed algorithm. To alleviate the effect of occasional factors, we repeat the experiment six times and average the results of them. We show the details in the following.


### 5.2. Network Lifetime

Network lifetime is the most important evaluating indicator of the design of WSN, which is the higher the better. The network lifetime is depended on the node consuming the most energy, which is defined in Equation (4). As shown in Table 3, we first compare the proposed method with WRP and EAPC which are based on the strategy of step-by-step rendezvous selection. One can find that the proposed strategy of electing the set of rendezvous points directly outperforms the step-by-step schema. The average improvements of network lifetime are 29.785 (about 23.2%) and 11.49 (about 10.5%) rounds under the BD and UD scenarios, respectively. We also compare the proposed method with DDR, WRP, EAPC, and ACO in the figure, and the results are illustrated in Figure 3. The results show that our proposed method helps to prolong the network lifetime and provides competitive performance with the ant colony optimal-based method. From the results, one can also see that the network gets saturated when the number of nodes exceeds 500. Actually, the capacity of network is depended on the configuration of the battery energy of each node and the energy consumption model.Table 3
Comparison with other methods based on step-by-step rendezvous point selection in terms of network lifetime (round).
# of sensor100200300400500600AvgBD (Lmax=600)WRP299.6257.0127.6517.7117.9011.7371.94EAPC410.5889.3448.2724.5024.3414.90101.99Ours481.14107.8564.1134.2231.9719.99123.21BD (Lmax=800)WRP536.69107.9742.2435.1727.1920.71128.33EAPC591.79139.0571.7054.9139.8229.27154.42Ours718.82195.7084.9769.1050.1737.86192.77UD (Lmax=600)WRP184.4136.9317.5910.228.006.0443.87EAPC291.2985.5839.8625.7220.5513.9179.48Ours325.1189.6345.1729.6324.0616.5888.36UD (Lmax=800)WRP477.8281.2331.4518.1312.578.99105.03EAPC585.47114.2350.6432.9225.6621.10138.34Ours616.16145.5660.4438.6228.9924.87152.44Figure 3
Network lifetime. The proposed method outperforms other methods based on the strategy of step-by-step rendezvous selection and achieves the competitive performance with the ACO-based end-to-end method.
(a)
BD (Lmax=600)(b)
BD (Lmax=800)(c)
UD (Lmax=600)(d)
UD (Lmax=800)


### 5.3. Total Energy Consumption

We also compare our proposed method with other methods in terms of total energy consumption, which is defined as the sum of energy consumption of all nodes. For simplicity, we assume that the energy consumption occurs only when sensor nodes transmit and receive data. Figure4 shows the comparison between the proposed method and other approaches. From the figure, one can find that the proposed method reaches a comparable performance in terms of total energy consumption. The proposed method has less energy consumption than the ACO. When the scale of WSN is large, the proposed method seems to consume more energy than DDR, which collects data with static sink. The reason is that there is additional energy consumption when transmitting data from node located in base station to the mobile sink. However, it can be negligible as compared to the energy consumption occurred in energy-hole problem.Figure 4
Total energy consumption. The proposed method provides a strategy that consumes less energy per round than other methods using the mobile sink.
(a)
BD (Lmax=600)(b)
BD (Lmax=800)(c)
UD (Lmax=600)(d)
UD (Lmax=800)


### 5.4. Fairness Index

The balance of energy consumption between sensor nodes also impacts the network lifetime significantly, where more balanced energy consumption results in longer network lifetime. The fairness index describes the degree of balance, which is defined as(9)FI=∑i=0nndi+12n+1×∑i=0nndi+12,where n and ndi denote the number of sensor nodes and the number of child nodes of node i, respectively. We compare the proposed method with WRP, EAPC, and ACO which are mobile sink-based algorithm in terms of FI, and the result is shown in Figure 5. From the figure, one can find that our proposed method reaches a higher fairness index than WRP and EAPC.Figure 5
FI. The proposed method obtains a better balance of energy consumption between sensor nodes than other methods with step-by-step rendezvous selection.
(a)
BD (Lmax=600)(b)
BD (Lmax=800)(c)
UD (Lmax=600)(d)
UD (Lmax=800)


### 5.5. Efficient Index

The design of WSN with mobile sink is mostly constrained by the time-delay, which can reformulate the touring length constraint for mobile sink. Taking full use of the length constraint can help to prolong the network lifetime. The efficient index defines the degree of full use of maximum allowed length, which is also the higher the better and formulated as(10)EI=1.0−1.0−LLmax×LNrp,where L, Lmax, and Nrp are the actual touring length, maximum allowed length, and the number of rendezvous points, respectively. Figure 6 compares the EI between three methods, and the result shows that the proposed method has a better efficient index than other methods.Figure 6
EI. The proposed method fully utilizes the available touring length, which helps to save the total energy consumption.
(a)
BD (Lmax=600)(b)
BD (Lmax=800)(c)
UD (Lmax=600)(d)
UD (Lmax=800)


### 5.6. Running Time

As for complexity, we compare the running time of four methods in Figure7. Since the proposed method has to update the voting score iteratively to converge to a better solution, it is more time consuming, which is suitable in offline situation instead of the real time. However, when the number of nodes increases, the time overhead is smaller than the ant colony optimal-based method which is also an iterative algorithm.Figure 7
Running time. Since the proposed method is an iterative approach, it is more time consuming and is only suitable for the offline situations. However, when the number of nodes increases, the running time of the proposed method is less than the ACO-based end-to-end method which is also an iterative method.
(a)
BD (Lmax=600)(b)
BD (Lmax=800)(c)
UD (Lmax=600)(d)
UD (Lmax=800)


### 5.7. Visualization of Score Update

To further illustrate the difference between the proposed method and other method, we visualize the results of EAPC and the MV-based method with different times of score update. The results are depicted in Figure8, where the base station is drawn in blue point, the touring path of mobile sink is drawn in red line, and nodes in the same tree are drawn in the same color. From the figure, one can see that the scale of trees is more balanced in the MV-based method, and the procedure of score update tends to choose the tree with more nodes and break it into several trees with smaller scale.Figure 8
Visualization of results: UD (Lmax=600). With the number of iterations increasing, a better result with longer network lifetime can be obtained.
(a)
EAPC (68.44 rounds)(b)
MV: iter. 1 (70.17 rounds)(c)
MV: iter. 8 (73.90 rounds)(d)
MV: iter. 16 (87.95 rounds)(e)
MV: iter. 32 (93.89 rounds)


## 5.1. Experimental Setup

To benchmark our proposed algorithm, we have conducted extensive experiments using simulator written in Python. We consider a WSN with the monitoring field of size300×300 m2, where the sensor nodes are distributed randomly in the field and the number of sensors varies from 100 to 600. Two types of distribution are implemented:
(i)
Balanced distribution (BD): all the sensors are uniformly distributed in the monitoring filed(ii)
Unbalanced distribution (UD): the monitoring field is divided into3×3 squares, where each squares is 100×100 m2 in size. Five squares are chosen to deploy sensors randomly, where the squares do not share the edge with each otherIn addition, the communication range of sensors is set to 30 m, and the moving velocity of the mobile sink is 1 m/s. Each sensor can communicate with other sensors and MS, which are located in the communication range, through one hop. The initial energy of each sensor isEi=100 J, and the energy consumption for transmitting and receiving one data packet is Et=0.021 J and Er=0.015 J, respectively. The configuration of network is detailed in Table 2.Table 2
The configuration of network.
DescriptionValueSimulatorPythonNode deploymentRandomNetwork area300m×300m# of sensor nodes100-300Communication range30 mEt0.021 JEr0.015 JE0100 JVelocity of mobile sink1m/sTo validate the effectiveness of the proposed method, we compare it with other SOTA methods: dynamic directional routing (DDR) [29], weighted rendezvous planning (WRP) [24], energy-aware path construction (EAPC) [23], and end-to-end ant colony optimal- (ACO-) based rendezvous selection [30].
(i)
DDR is a novel routing protocol, which considers the mobility of sensor nodes. It is aimed at controlling the dataflow in the network to optimize the routes toward the sink. The DDR can effectively improve the network time and has the state-of-the-art performance under the scenario using static sink(ii)
WRP is an iterative greedy algorithm. At each iteration, each sensor is first weighted based on its hop distance to the closest rendezvous point and the number of nodes in the subtree rooted by the sensor. A sensor with maximum value of weight is selected as the rendezvous point. The iteration is terminated if the touring length exceeds the predefined maximum length(iii)
EAPC is similar to the WRP, which is a heuristic algorithm. It takes the Euclidean distance between sensor and its closest rendezvous point into consideration in addition. The EAPC algorithm reached an impressive performance with mobile sink(iv)
ACO is an end-to-end data collection strategy. It performs the rendezvous selection and touring planning simultaneously. The ACO algorithm provides a SOTA performance with a high computational complexityWe compare them without considering virtual rendezvous points for fairness. Several performance metrics, including network lifetime, total energy consumption, fairness index, efficient index, and running time, are used to comprehensively benchmark the proposed algorithm. To alleviate the effect of occasional factors, we repeat the experiment six times and average the results of them. We show the details in the following.


## 5.2. Network Lifetime

Network lifetime is the most important evaluating indicator of the design of WSN, which is the higher the better. The network lifetime is depended on the node consuming the most energy, which is defined in Equation (4). As shown in Table 3, we first compare the proposed method with WRP and EAPC which are based on the strategy of step-by-step rendezvous selection. One can find that the proposed strategy of electing the set of rendezvous points directly outperforms the step-by-step schema. The average improvements of network lifetime are 29.785 (about 23.2%) and 11.49 (about 10.5%) rounds under the BD and UD scenarios, respectively. We also compare the proposed method with DDR, WRP, EAPC, and ACO in the figure, and the results are illustrated in Figure 3. The results show that our proposed method helps to prolong the network lifetime and provides competitive performance with the ant colony optimal-based method. From the results, one can also see that the network gets saturated when the number of nodes exceeds 500. Actually, the capacity of network is depended on the configuration of the battery energy of each node and the energy consumption model.Table 3
Comparison with other methods based on step-by-step rendezvous point selection in terms of network lifetime (round).
# of sensor100200300400500600AvgBD (Lmax=600)WRP299.6257.0127.6517.7117.9011.7371.94EAPC410.5889.3448.2724.5024.3414.90101.99Ours481.14107.8564.1134.2231.9719.99123.21BD (Lmax=800)WRP536.69107.9742.2435.1727.1920.71128.33EAPC591.79139.0571.7054.9139.8229.27154.42Ours718.82195.7084.9769.1050.1737.86192.77UD (Lmax=600)WRP184.4136.9317.5910.228.006.0443.87EAPC291.2985.5839.8625.7220.5513.9179.48Ours325.1189.6345.1729.6324.0616.5888.36UD (Lmax=800)WRP477.8281.2331.4518.1312.578.99105.03EAPC585.47114.2350.6432.9225.6621.10138.34Ours616.16145.5660.4438.6228.9924.87152.44Figure 3
Network lifetime. The proposed method outperforms other methods based on the strategy of step-by-step rendezvous selection and achieves the competitive performance with the ACO-based end-to-end method.
(a)
BD (Lmax=600)(b)
BD (Lmax=800)(c)
UD (Lmax=600)(d)
UD (Lmax=800)


## 5.3. Total Energy Consumption

We also compare our proposed method with other methods in terms of total energy consumption, which is defined as the sum of energy consumption of all nodes. For simplicity, we assume that the energy consumption occurs only when sensor nodes transmit and receive data. Figure4 shows the comparison between the proposed method and other approaches. From the figure, one can find that the proposed method reaches a comparable performance in terms of total energy consumption. The proposed method has less energy consumption than the ACO. When the scale of WSN is large, the proposed method seems to consume more energy than DDR, which collects data with static sink. The reason is that there is additional energy consumption when transmitting data from node located in base station to the mobile sink. However, it can be negligible as compared to the energy consumption occurred in energy-hole problem.Figure 4
Total energy consumption. The proposed method provides a strategy that consumes less energy per round than other methods using the mobile sink.
(a)
BD (Lmax=600)(b)
BD (Lmax=800)(c)
UD (Lmax=600)(d)
UD (Lmax=800)


## 5.4. Fairness Index

The balance of energy consumption between sensor nodes also impacts the network lifetime significantly, where more balanced energy consumption results in longer network lifetime. The fairness index describes the degree of balance, which is defined as(9)FI=∑i=0nndi+12n+1×∑i=0nndi+12,where n and ndi denote the number of sensor nodes and the number of child nodes of node i, respectively. We compare the proposed method with WRP, EAPC, and ACO which are mobile sink-based algorithm in terms of FI, and the result is shown in Figure 5. From the figure, one can find that our proposed method reaches a higher fairness index than WRP and EAPC.Figure 5
FI. The proposed method obtains a better balance of energy consumption between sensor nodes than other methods with step-by-step rendezvous selection.
(a)
BD (Lmax=600)(b)
BD (Lmax=800)(c)
UD (Lmax=600)(d)
UD (Lmax=800)


## 5.5. Efficient Index

The design of WSN with mobile sink is mostly constrained by the time-delay, which can reformulate the touring length constraint for mobile sink. Taking full use of the length constraint can help to prolong the network lifetime. The efficient index defines the degree of full use of maximum allowed length, which is also the higher the better and formulated as(10)EI=1.0−1.0−LLmax×LNrp,where L, Lmax, and Nrp are the actual touring length, maximum allowed length, and the number of rendezvous points, respectively. Figure 6 compares the EI between three methods, and the result shows that the proposed method has a better efficient index than other methods.Figure 6
EI. The proposed method fully utilizes the available touring length, which helps to save the total energy consumption.
(a)
BD (Lmax=600)(b)
BD (Lmax=800)(c)
UD (Lmax=600)(d)
UD (Lmax=800)


## 5.6. Running Time

As for complexity, we compare the running time of four methods in Figure7. Since the proposed method has to update the voting score iteratively to converge to a better solution, it is more time consuming, which is suitable in offline situation instead of the real time. However, when the number of nodes increases, the time overhead is smaller than the ant colony optimal-based method which is also an iterative algorithm.Figure 7
Running time. Since the proposed method is an iterative approach, it is more time consuming and is only suitable for the offline situations. However, when the number of nodes increases, the running time of the proposed method is less than the ACO-based end-to-end method which is also an iterative method.
(a)
BD (Lmax=600)(b)
BD (Lmax=800)(c)
UD (Lmax=600)(d)
UD (Lmax=800)


## 5.7. Visualization of Score Update

To further illustrate the difference between the proposed method and other method, we visualize the results of EAPC and the MV-based method with different times of score update. The results are depicted in Figure8, where the base station is drawn in blue point, the touring path of mobile sink is drawn in red line, and nodes in the same tree are drawn in the same color. From the figure, one can see that the scale of trees is more balanced in the MV-based method, and the procedure of score update tends to choose the tree with more nodes and break it into several trees with smaller scale.Figure 8
Visualization of results: UD (Lmax=600). With the number of iterations increasing, a better result with longer network lifetime can be obtained.
(a)
EAPC (68.44 rounds)(b)
MV: iter. 1 (70.17 rounds)(c)
MV: iter. 8 (73.90 rounds)(d)
MV: iter. 16 (87.95 rounds)(e)
MV: iter. 32 (93.89 rounds)


## 6. Conclusion and Future Work

In this paper, we proposed the MV-based rendezvous point selection approaches, which considers implicitly the touring length constraint during rendezvous point selection and “votes” the solution (a set of rendezvous points) directly. Extensive experiments demonstrate that the proposed method helps to balance the energy consumption among nodes and further prolong the network lifetime.As a future work, we plan to extend the proposed method to a more general model with deep reinforcement learning, which have been widely applied in many fields but less explored in rendezvous point selection of WSN. The further performance improvement and the generalization capability could be expected due to the powerful modeling capacity of neural network.



---

*Source: 8245306-2022-12-12.xml*