# Delay Tolerance and Energy Saving in Wireless Sensor Networks with a Mobile Base Station

Authors: Oday Jerew; Nizar Al Bassam
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

Recent research shows that significant energy saving can be achieved in wireless sensor networks by using mobile devices. A mobile device roams sensing fields and collects data from sensors through a short transmission range. Multihop communication is used to improve data gathering by reducing the tour length of the mobile device. In this paper we study the trade-off between energy saving and data gathering latency in wireless sensor networks. In particular, we examine the balance between the relay hop count and the tour length of a mobile Base Station (BS). We propose two heuristic algorithms, Adjacent Tree-Bounded Hop Algorithm (AT-BHA) and Farthest Node First-Bounded Hop Algorithm (FNF-BHA), to reduce energy consumption of sensor nodes. The proposed algorithms select groups of Collection Trees (CTs) and a subset of Collection Location (CL) sensor nodes to buffer and forward data to the mobile BS when it arrives. Each CL node receives sensing data from its CT nodes within bounded hop count. Extensive experiments by simulation are conducted to evaluate the performance of the proposed algorithms against another heuristic. We demonstrate that the proposed algorithms outperform the existing work with the mean of the length of mobile BS tour.


---

## Body

## 1. Introduction

Data gathering in Wireless Sensor Networks (WSNs) is one of the most frequent and fundamental operations, which requires the sensor nodes to monitor the sensing field for as long as possible. As sensor nodes have limited energy resources and are powered by small batteries, energy consumption is a critical issue in the design of WSNs that affect the energy consumption of sensor nodes and hence the network lifetime.Recent research [1–5] shows that significant energy saving can be achieved in wireless sensor networks by using mobile devices capable of carrying data mechanically. Mobile Base Stations (BSs) are proposed to reduce energy consumption by allowing a mobile BS to roam a sensing field and gather data from sensor nodes through a short transmission range. The energy consumption of each sensor node is then reduced, since fewer relays are needed for the sensor node to relay its data packet to the BS. As the speed of mobile BS is very slow compared with the speed of data packets, which travel in multihop forwarding, the increased latency of data gathering when employing mobile BS presents a major performance bottleneck. Consequently, the time a mobile BS takes to tour a large sensing field may not meet the stringent delay requirements inherent in some mission-critical, real-time applications. Therefore, planning the tour of mobile BS needs to be considered in order to achieve the delay requirements.Generally, the mobility of BS can be classified into three types, according to the mobility pattern of the entity upon which the BS is mounted, as follows:(1)
Random mobility: this can be achieved, for example, when the BS is mounted on humans and animals. In this case, the probability of the BS collecting all sensing data is low since the BS opportunistically visits sensor nodes [6].(2)
Predictable mobility: in this case, the BS is mounted on an entity that moves on a fixed track or path that cannot control its direction or speed, but which moves at a regular time, for example, a BS mounted on a bus or train. Thus, the sensor nodes can predict when the BS may move around to send their data [7, 8].(3)
Controlled mobility: when the BS is mounted on a robot or UAV plane, then the direction and speed of the BS can be controlled. Many algorithms are proposed to find the tour of the BS in order to achieve requirements such as maximised network lifetime and data-gathering delay using single and multihop relays [3, 5, 9].Most literature studies the mobility of WSNs to be predictable or controlled to achieve network performance requirements (some literature focused on random mobility to improve network lifetime). This differs from mobile ad hoc networks in which nodes are assumed to move arbitrarily, which degrades the network performance by link failures.In this paper, we deal with the data gathering problem with bounded delay time in sensor network using a controlled mobile BS, by exploring a balance between the relay hop count required for data relay and tour length of the mobile BS such that the energy consumption is minimized. Specifically, we assume the mobile BS selected a set of Collection Location (CL) nodes that temporarily cache and forward sensing data of other nodes. The sensor nodes are grouped into Collection Trees (CTs) rooted at CLs. Each node has to forward its data to the CL within a certain number of relay hops. The mobile BS traverses along a close tour and stops at each CL in the tour for data gathering.Our major contributions, in this paper, are as follows. We propose two efficient heuristic algorithms: Adjacent Tree-Bounded Hop Algorithm (AT-BHA) and Farthest Node First-Bounded Hop Algorithm (FNF-BHA). The algorithms find the tour of the mobile BS consisting of CLs which meet the following criteria: (i) the energy consumption among the sensor nodes is balanced in order to prolong nodes lifetime; (ii) the total traversal time of the mobile BS on the tour is minimized; and (iii) the hop count between any sensor node and the CL is bounded by a given value. The AT-BHA constructs adjacent CTs by finding closest nodes to the last constructed CL. The FNF-BHA uses the farthest node from the BS in the construction of CL. Load balancing algorithm is proposed to balance the number of nodes in the CTs. Finally, the performance of the proposed algorithms is evaluated through experimental simulations. The experimental results demonstrate that the proposed algorithms are efficient.The remainder of this paper is organized as follows. Section2 reviews the related work on mobile data gathering. Section 3 presents two algorithms to solve data gathering with bounded hop count problem. Section 4 evaluates the efficiency of the proposed algorithms through extensive simulations. Finally, Section 5 concludes the paper.


## 2. Related Work

There is an extensive range of literature studying the use of mobile BS for data gathering [4, 5, 9–15]. Kansal et al. [12] combine multihop forwarding with a mobile BS. They performed an experimental evaluation for a small sensor network, assuming that a mobile BS moves back and forth on a straight line (a fixed path). They employed a directed diffusion approach to gathering sensed data from the sensor nodes beyond the transmission range of the mobile BS.Some existing studies assume that sensor nodes can cache sensing data of other nodes in order to forward it to the mobile BS when the BS moves around. Gao and Zhang [11] and Xing et al. [16] explored the delay requirement for data gathering assuming that the sensor nodes have an ability to cache sensing data of other nodes. In [11] sensor nodes send their data through multihop relays to the nodes (subsink) located within the direct-transmission range of the mobile BS. The subsink nodes cache data and send it to the mobile BS when it comes within transmission range. In [16], a rendezvous-based data-gathering approach is proposed, in which a subset of nodes is chosen as rendezvous points. The role of these points is to buffer and aggregate data originating from sensor nodes. When the mobile BS arrives within the transmission range of rendezvous points, the data will be forwarded to the mobile BS. Kaswanet et al. [17] proposed path plan algorithm for data collection by selecting set of rendezvous points. The algorithm minimize the tour length by reducing the number of rendezvous points by selecting the position closest to the location of the BS and allows the BS to collect data from maximum number of sensors via single hop communication. This algorithm does not consider a bounded hop count for data collection.Grouping sensor nodes in the sensing field into clusters and collecting data from cluster heads are proposed in [13–15]. Ma and Yang [13] proposed a heuristic for finding routing paths for the mobile BS, which assumes that the moving path of the mobile BS consists of a series of line segments. Sensor nodes closest to each line segment are selected as cluster heads. A specified configuration is applied, where the mobile BS starts data gathering from the left side of the path, moves towards the right side, and then comes back to the left side again. This scheme maximizes network lifetime. However, it may cause packet losses at each cluster head if the path length to the cluster head is too long, since the time required for the cluster head to send the data of cluster nodes to the BS is not considered in cluster forming. Saad et al. [14] proposed path planning algorithm for mobile BS that visit a set of cluster heads. Nodes are randomly grouped to form clusters and the node with the largest residual energy is selected as the cluster head. The clusters are merged, ensuring that the number of hops from the cluster head to any cluster node is no more than two hops. The cluster head gathers and buffers cluster sensing data. The BS visits the cluster heads to gather data through single-hop communication. However, this work does not consider data gathering delay for the mobile BS. Zhang et al. [15] extended the work in [16] and regarded cluster heads as the rendezvous point. They considered event based data gathering and proposed reduction in data gathering delay by only allowing the mobile BS to visit cluster heads that generate new data.Bounded hop count for data gathering is studied in [4, 5, 18, 19]. Zhao and Yang [5] proposed SPT-DGA and BRH-MDG data gathering algorithms that select set of CL for the mobile BS to visit for data gathering. Each CL aggregates the local data from its affiliated sensors within a certain number of relay hops. However, the number of nodes in the constructed CT is small. Consequently, many CTs are constructed for data gathering. Thus, the length of the BS tour increased. Chen et al. [19] analysed and improved the BRH-MDG algorithm by minimizing the degree of the CTs in order to prolong the network lifetime. Xu et al. [4] proposed heuristic algorithm to find the tour for a mobile BS consists of CL nodes. However, the algorithm does not consider the effect of some critical sensor nodes on the separation of other nodes. These critical nodes affect the location of CLs and hence the length of the mobile BS. The hop count and hop distance are used to plan the route of the mobile BS in [18]. In this work, set of rendezvous points are selected such that the mobile BS can collect data from the sensor nodes within a permissible delay with minimum possible hop distance and hop counts. However, this work does not consider minimizing the BS tour length.Dividing sensing field into subareas is proposed in [20, 21]. Chen et al. [20] introduced algorithm to improve the network lifetime considering data transmission delay and number of hops. The algorithm divided the sensing field into grids; the mobile sink has to stay at the grid center for data collection. However, this work assumes the sensor nodes send data to the BS only when the hop count between the sensor and the BS is at or below a specific hop count. Otherwise the sensor enters a sleeping state. In addition, the hop count is estimated using the distance between the sensor nodes and the BS which is not accurate at low node density (node degree less than six). A delay bound path algorithm is proposed in [21]. The algorithm divided the sensing field into hexagonal cells whose centers are considered as the positions of rendezvous point. The algorithm minimizes the number of rendezvous point by selecting the location that covers as many number of sensor nodes and at minimal distance from the center. Data gathering within bounded hop count is also studied in [22]. The authors proposed reducing the number of collection points by selection of the CL within the convergence area that overlaps maximum number of sensor nodes. However, the work in [21, 22] does not consider the effect of isolated sensor nodes on the tour length of the BS.Other literature involved sensor node residual energy and bounded hop count in the construction of the data gathering trees [2, 23]. Zhu et al. [23] suggested assigning weight for each node based on nodes residual energy, distance to the BS and number of hops. The weight is used to select rendezvous points for data collection. Jerew and Al Bassam [2] examined the sensor nodes residual energy to select a set of cluster heads with high residual energy and bounded hop count. Sensor node sends its data within bounded hop count to the cluster head and the BS visits all the cluster heads for data gathering. Chang and Shen [24] introduced a cluster routing structure, to decide the routing path based on the location of BS, the distances between the sensor nodes, and the residual energy of each sensor node. The closest node to the BS with residual energy more than the average network residual energy is selected as cluster head. The proposed algorithm reduced the energy consumption and extended the sensor lifetime by balancing the network load. However, this work did not consider data gathering within a bounded hop count.


### 2.1. Preliminaries and Problem

We consider a wireless sensor networkG=(V,E) consisting of n=|V| stationary sensors and E is the set of links. There is a link between two sensors or a sensor and the BS if they are within the transmission range of each other. For the sake of simplicity, we assume the transmission range of each sensor node and the BS are fixed and identical, and all sensor nodes have identical initial energy. The storage of a sensor node is limited, so that it cannot buffer a large volume of data. Sensor nodes are densely deployed in the sensing region. Accordingly, the number of hops in a path is approximately proportional to the distance between the nodes. The BS moves with constant velocity. Thus, there is sufficient time to establish communication and send one or more data packets during the time the BS takes to travel across the transmission range of a sensor node. We further assume the mobile BS replenishes its energy periodically so there is no energy concern with the mobile BS. Finally, sensor nodes and the mobile BS are assumed to know their own physical locations via GPS or a location service in the network.Problem. Given a network with a mobile BS and assuming that the number of hops for data gathering between the BS and sensor nodes is bounded by h, the problem is to find the shortest tour for the mobile BS such that the energy consumption among the sensor nodes is balanced.


## 2.1. Preliminaries and Problem

We consider a wireless sensor networkG=(V,E) consisting of n=|V| stationary sensors and E is the set of links. There is a link between two sensors or a sensor and the BS if they are within the transmission range of each other. For the sake of simplicity, we assume the transmission range of each sensor node and the BS are fixed and identical, and all sensor nodes have identical initial energy. The storage of a sensor node is limited, so that it cannot buffer a large volume of data. Sensor nodes are densely deployed in the sensing region. Accordingly, the number of hops in a path is approximately proportional to the distance between the nodes. The BS moves with constant velocity. Thus, there is sufficient time to establish communication and send one or more data packets during the time the BS takes to travel across the transmission range of a sensor node. We further assume the mobile BS replenishes its energy periodically so there is no energy concern with the mobile BS. Finally, sensor nodes and the mobile BS are assumed to know their own physical locations via GPS or a location service in the network.Problem. Given a network with a mobile BS and assuming that the number of hops for data gathering between the BS and sensor nodes is bounded by h, the problem is to find the shortest tour for the mobile BS such that the energy consumption among the sensor nodes is balanced.


## 3. Proposed Heuristic Algorithms

Due to the NP-hardness of this problem [5], a heuristic algorithm is proposed in this paper. In order to find the optimal CLs among sensors, relay routing paths and the tour of the mobile BS should jointly be considered. Based on these observations, we deal with the tour length minimization problem by devising scalable heuristic algorithms. In this section, we proposed two algorithms: the Adjacent Tree-Bounded Hop Algorithm (AT-BHA) and the Farthest Node First-Bounded Hop Algorithm (FNF-BHA). Table 1 shows the main symbols used in the proposed algorithms.Table 1
Definitions of the main symbols used throughout the algorithms.
Symbol Description V Set of network nodes  β Between -1 and 1, to calculate hop progress  τ Threshold value to decide tree update  h Number of hops  TP Set of nodes in a partition tree  vc Root node of the MST that is closest to the location of BS  vf Farthest node from the BS  R(vf,vc) Set of nodes in the routing path betweenvf and vc  vCL Set of the collection location nodes  TCj,h Set of nodes contained in the partialjth tree within h hops away from the root  NP Set of the nodes at network partition tree  d(v1,v2) Euclidean distance between verticesv1 and v2  nf Farthest node to the BS and closest to theTCj,h tree  r Transmission range of a sensor node  Nr Set of nodes to be removed from a tree


### 3.1. Adjacent Tree-Bounded Hop Algorithm (AT-BHA)

The basic idea of AT-BHA algorithm is to find a set of CLs in the network that the BS can visit to collect sensing data of all the sensors. Visiting CLs in specific order determines the length of the tour of the mobile BS. The value ofh determines the delay on data delivery and affects the number of sensor nodes contained in each tree and, hence, the number of CLs. For example, if h=1 the number of CLs is equal to the number of sensor nodes and the BS tour is the longest tour as the BS has to visit each node for one hop data collection.In any network, the node degree (number of neighbor nodes) significantly affects the network connectivity. As the node degreed<6, there is a high probability of partitioned networks [25]. The first task of AT-BHA as shown in Algorithm 1 is to construct Minimum Spanning Trees (MSTs) that cover all sensors in the network. Each sensor node associated in a single MST referred to as TP. Thus, the AT-BHA can be applied to connected and disconnected networks.Algorithm 1:The Adjacent Tree-Bounded Hop Algorithm (AT-BHA).
Input: A sensor network G(V,E), hop cout h, r, β Output: Set of CL nodes vCL, BTC (1)NG←V; /∗set of nodes in the network ∗/; (2)k=0; (3)j=0; (4)while  NG  is not empty  do (5)Find the closest vertex vc to the BS position from NG; (6)Find an MST TP that covers vertices from NG; (7)NP←TP; /∗ set of nodes in partition tree TP∗/   ; (8)while  NP  is not empty  do (9)Find the farthest leave vertex vf in TP; (10)Find the routing path R(vf,vc); (11)if  h≥Rvf,vc  then (12)vCL←vc; (13)else (14)vCL← vertex from R(vf,vc) at h hops from vf; (15)j=j+1; (16)Find an MST TCj,h(vCL,NP); (17)NP←NP-TCj,h; (18)if  NP  is empty  then (19)break; (20)Find nf node that with Max.{d(NP,vc)/d(NP,vCL)}; (21)Find Ncr set of nodes with d(NP,nf)≤hrβ; /∗ nodes within a circle of hrβ radius /∗; (22)Find the closest vertex vn to vc from Ncr; (23)j=j+1; (24)vCL←vn; /∗ set vn as a CL ∗/  ; (25)Find an MST TCj,h(vCL,NP); (26)NP←NP-TCj,h; (27)(TC,NP)=Update_CT(vCL,j,NP,TC,TP)   ; (28)NG←NG-NP (29) [BTC, vCL]=Call LBA(vCL)   ;The root of the MST is selected at sensor nodevc that is the closest to the location of the BS. We set the root close to the BS in order to select CLs as close as possible to each other and close to the BS initial position.The next task of AT-BHA is to find the farthest node,vf, from the BS position in the partition tree. The routing path between the farthest node and root of TP is referred to as R(vf,vc) and it is used to find the candidate CL node. We assume the set of nodes in R is sorted in decreasing order according to the number of hops to vc. In the case of the number of nodes in the routing path being less than h, then the root of the TP tree is selected as vCL. While the node at h hop away from the vf is selected as vCL if the route length is higher than h.The Breath-First-Search (BFS) algorithm with bounded hop count is used to find the Minimum Spanning Tree (MST) rooted at the CL. A partial BFS tree is constructed hop by hop, and the expansion continues until all nodes withinh hops are explored. The set of sensors contained in the partial jth tree is referred to as TCj,h. The set of the nodes covered in the jth CT is removed from the set of partition tree nodes, NP.In this algorithm, we propose to find the next CT adjacent to the last constructed tree in order to avoid partitioned node between the CTs. The partitioned node increases the tour length since the BS has to visit the node for data collection. To find an adjacent tree to thejth tree, the algorithm calculates the ratio α=d(NP,vc)/d(NP,vCL). The d(v1,v2) represents Euclidean distance between vertices v1 and v2. The node from NP with maximum α is selected and referred to as nf. This node represents the farthest node to BS and closest to the TCj,h. The closest node to the BS that is within the distance hrβ from nf is selected as the second vCL, where r is the sensor transmission range and β between -1 and 1. The value rβ represents the hop progress and its ranges from -r to r depend on the network node density [25]. New MST is constructed rooted at vCL to find set of nodes within h hops.The number of nodes within each tree and the position of the CL nodes have a signification effect on the tour length. When the CT consists of many nodes, a less number of CLs are required and the tour length decreases. In addition, the tour length is also decreased as the selected CLs are close to the BS. To improve the tree size and location ofvCL, the Update_CT algorithm is proposed in Algorithm 2.Algorithm 2:Update_CT.
Input: vCL, j, NP, TC, TP, τ Output: TC,NP (1)if  vCL  is the first time for check  then (2)NCL←TCj,h; (3)if  |NCL|/d(vCL,vc)≤τ  then (4)Find the routing path R(vCL,vc) using partition tree TP; (5)if  h≥RvCL,vc  then (6)NP←NP∪R(vCL,vc); (7)vCL←vc; (8)else (9) Find vertex vh from R(vCL,vc) at h hops from vCL; (10)NP←NP∪R(vCL,vh); (11)vCL←vh; (12) (13)Find an MST TCj,h(vCL,NP); /∗ Update the j-th tree∗/   ; (14)NP←NP-TCj,h; (15) Return(TC,NP)In the Update_CT algorithm, the ratio of the number of tree nodes to the distance between thevCL and vc is used as a measure of tree usefulness. A threshold value, τ, is used to decide the updating of the CT. The range of τ is (1/d(LBS,NF),n/d(LBS,vBS)), where n is the network nodes, and LBS, vBS, and NF are, respectively, the position of BS, the closest node to the BS, and the farthest node to the BS.In order to avoid infinite looping, the algorithm first checks whether the CT is previously updated since in some cases it is impossible to update the tree because of limited number of nodes. In the case the CT needs to update, the routing path betweenvCL and vc is used to select a new CL node. NP is updated by including the set of CT nodes and the set of routing nodes to the selected vCL. Finally, the updated CT is constructed and returns the updated CT and NP to the AT-BHA algorithm. The AT-BHA algorithm continues until all the network nodes are associated with CTs.


### 3.2. Farthest Node First-Bounded Hop Algorithm (FNF-BHA)

This algorithm constructs CTs to include the farthest nodes to the BS. The FNF-BHA starts similar to AT-BHA by finding the nodes closest to the position of the BS and construction partitions trees. It then finds the route of data packets tovf in the current partition tree to determine the CL node. The nodes involved in the data relay between vf and the collection node are critical for data gathering from vf. In the case of any of the relay node participating in another CT, the BS has to visit vf for data collection increasing the tour length. Therefore, in this case, the algorithm first identifies and then removes all the relay nodes from other CTs by calling the Node Removal Algorithm (NRA) as shown in Algorithm 3. The set of removed nodes is used in the construction of new CTs at the next iteration.Algorithm 3:The Farthest Node First-Bounded Hop Algorithm (FNF-BHA).
Input: A sensor network G(V,E), hop cout h Output: Set of CL nodes vCL, BTC (1)NG←V   ;/∗set of nodes in the network∗/   ; (2)while  NG  is not empty  do (3)Find the closest vertex vc to the BS position from NG; (4)Find an MST Tp that covers vertices from NG; (5)NP←TP; set of nodes in partition tree Tp   ; (6)while  NP  is not empty  do (7)Flag ← false   ; /∗no node need to remove from any tree   ; (8)Find the farthest leave vertex vf to vc on Tp; (9)Find the routing path R(vf,vc); (10)if  h≥|R(vf,vc)|  then (11)vCL←vc; (12)else (13)vCL← vertex from R(vf,vc) at h hops from vf; (14)Nr← set of nodes in R(vf,vcL) not in NP; (15)if  Nr  is not empty  then (16)Flag ← true   ; (17)Nrm= NRA(Nr,NP); /∗ call Node Removal Algorithm ∗/ N P ← N P ∪ N r m; (18)if  Flag= false  then (19)if  vCL  selected as  CL  then (20)j=index of tree rooted on vCL; (21)NP←NP∪TCj,h;; (22)else (23) select vCL as Collection Location   ; (24)j=j+1; (25) (26)Find an MST TCj,h(vCL,NP); (27)NP←NP-TCj,h; (28)NG←NG-NP; (29) [vCL,BTC]=Call LBA(vCL)   ;The algorithm tests whether the CL node is already selected as CL of another tree. In this rare case, the set of CT nodes are merged with that tree and new CT is constructed. The new tree includes all the nodes of previous CT in addition tovf, since all the relay nodes are available in the set of nodes, whereas, if the CL node is not selected, a new CT is constructed with a new tree index to include vf. The algorithm is terminated when all the partitioned tree nodes are covered.We now describe NRA algorithm in more detail. The pseudocode is given in Algorithm4. In order to remove the set of nodes in Nr from the CTs, the tree index of each node needs to be found first. The set of nodes that need to be removed from each CT are identified and removed. A new CT is reconstructed after node removal. In some cases, some of the tree nodes, No, are partitioned, since the removed nodes provide a relay path for them. No may be covered by other CTs. Therefore, all the CTs are reconstructed considering No. If a node is associated with CT, the node is removed from No. The algorithm continues until all the nodes in Nr are removed from the CTs.Algorithm 4:Node Removal Algorithm (NRA).
Input: A sensor network G(V,E), hop cout h, Nr, NP Output:  Nr, TC (1)IX← set of tree index of all CTs   ; (2)IXrt← set of tree index of all Nr nodes   ; (3)Nrm←ϕ; (4)No←ϕ; (5)for  each  j  in  IXrt  do (6)Nrt←Nr∩TCj,h∗/ Set of nodes to remove from the j-th tree ∗/  ; (7)Nnt←TCj,h-Nrt;∗/ Set of node of the j-th tree after node removel ∗/   ; (8)get vCL from tree j; (9)Find an MST TCj,h(vCL,Nnt); (10)NP←Nnt-TCj,h;∗/ Set of partitioned nodes ∗/   ; (11)No←No∪NP; (12)if  Nois not empty  then (13)for  each  tree  indexk  in  IX  do (14) get vCL for tree k; (15)nt←TCk,h; (16)nset←TCk,h∪No; (17) Find an MST TCk,h(vCL,nset); (18)Ndif←TCk,h-nt; (19)No←No-Ndif; (20)Nrm←Nrm∪Nrt∪No; (21) Return(Nrm)   ;


### 3.3. Load Balancing and Further Improvement

The proposed algorithms AT-BHA and FNF-BHA can be further improved by balancing the number of nodes in the CTs. The proposed algorithms find the set of CL nodes to collect data from sensor nodes withinh hops. However, there are large differences between the number of nodes in the CTs. In particular, the first constructed tree covers the maximum number of nodes, while the last tree covers only the remaining set of nodes.Thus, we proposed the load balanced algorithm (LBA) with the pseudocode given in Algorithm5. First, the algorithm balanced the number of nodes for each CT using the CT balanced algorithm (CTBA) shown in Algorithm 6. The CTBA first sorts the CTs in increasing order according to the number of nodes in order to start constructing the CT with the minimum number of nodes. The algorithm gradually constructs all the CTs by finding the nodes with one hop from the CL nodes. Then the number of nodes in the CTs increases with the hop count. In some cases, some nodes does not associate to any tree since they are partitioned as the relaying nodes are associated to other CTs. Finally, the LBA returns the balanced CTs (BTC) and partitioned nodes (PN). When there is no PN the algorithm finalizes the BTC and no further process is required. However, a new set of vCL needs to be selected from the PN for data collection. This is achieved by finding the farthest node vf to the BS from PN. The routing path between vf and closest node to the BS is used to find the vCL at h hops. A new CT is constructed and rooted at vCL to cover PN nodes. Finally, the algorithm rebalanced the load by calling the LBA. The LBA is terminated when there is no partition node in the PN.Algorithm 5:Load balanced algorithm (LBA).
Input: A sensor network G(V,E), hop cout h, tree index j, TC Output: Set of CL nodes CL, BTC (1) [BTC,PN]=Call CTBA(G, TC)   ; (2)while  PN  is not empty  do (3)TC=BTC; copy all the CTs to TC; (4)j← number of trees in TC; (5)Find the farthest leave vertex vf from PN using TP; (6)Find the routing path R(vf,vc); (7)if  h≥|R(vf,vc)|   then (8)vCL←vc; (9)Rn←|R(vf,vc)|; (10)else (11)vCL← vertex from R(vf,vc) at h hops from vf; (12)Rn← nodes at h hops from Vf; (13)PN←PN∪Rn; (14)j=j+1; (15) Find an MST TCj,h(vCL,PN); (16)PN←PN-TCj,h; (17) [BTC,PN]=Call CTBA(G, TC)   ; (18) Return(CL, BTC)   ;Algorithm 6:CT balanced algorithm (CTBA).
Input: A sensor network G(V;E), Set of CTs TCj,h, hop count h Output: set of balanced CTs BTCj,h, Remain Nodes PN (1)K← number of CL nodes   ; (2)NG←V;/∗ set of nodes in the network ∗/   ; (3)NGB←NG; (4)BTCj,hc{j=1:K,hc=1:h}←ϕ; (5) SortTCj trees in increasing order according to the number of nodes in each tree   ; (6)NGB=NG-vCL // remove CL nodes from testing nodes   ; (7)for  hc= 1 to h  do (8)for  each  vCL  do (9)j=j+1; (10)if  hc>1  then (11)NGB=NGB∪BTCj,hc-1; (12)Find an MST BTCj,hc(vCL,NGB); (13)NGB=NGB-BTCj,hc /∗ remove tree nodes from testing nodes ∗/   ; (14)PN=NG-NGB; (15) Return(BTC,PN)   ;


## 3.1. Adjacent Tree-Bounded Hop Algorithm (AT-BHA)

The basic idea of AT-BHA algorithm is to find a set of CLs in the network that the BS can visit to collect sensing data of all the sensors. Visiting CLs in specific order determines the length of the tour of the mobile BS. The value ofh determines the delay on data delivery and affects the number of sensor nodes contained in each tree and, hence, the number of CLs. For example, if h=1 the number of CLs is equal to the number of sensor nodes and the BS tour is the longest tour as the BS has to visit each node for one hop data collection.In any network, the node degree (number of neighbor nodes) significantly affects the network connectivity. As the node degreed<6, there is a high probability of partitioned networks [25]. The first task of AT-BHA as shown in Algorithm 1 is to construct Minimum Spanning Trees (MSTs) that cover all sensors in the network. Each sensor node associated in a single MST referred to as TP. Thus, the AT-BHA can be applied to connected and disconnected networks.Algorithm 1:The Adjacent Tree-Bounded Hop Algorithm (AT-BHA).
Input: A sensor network G(V,E), hop cout h, r, β Output: Set of CL nodes vCL, BTC (1)NG←V; /∗set of nodes in the network ∗/; (2)k=0; (3)j=0; (4)while  NG  is not empty  do (5)Find the closest vertex vc to the BS position from NG; (6)Find an MST TP that covers vertices from NG; (7)NP←TP; /∗ set of nodes in partition tree TP∗/   ; (8)while  NP  is not empty  do (9)Find the farthest leave vertex vf in TP; (10)Find the routing path R(vf,vc); (11)if  h≥Rvf,vc  then (12)vCL←vc; (13)else (14)vCL← vertex from R(vf,vc) at h hops from vf; (15)j=j+1; (16)Find an MST TCj,h(vCL,NP); (17)NP←NP-TCj,h; (18)if  NP  is empty  then (19)break; (20)Find nf node that with Max.{d(NP,vc)/d(NP,vCL)}; (21)Find Ncr set of nodes with d(NP,nf)≤hrβ; /∗ nodes within a circle of hrβ radius /∗; (22)Find the closest vertex vn to vc from Ncr; (23)j=j+1; (24)vCL←vn; /∗ set vn as a CL ∗/  ; (25)Find an MST TCj,h(vCL,NP); (26)NP←NP-TCj,h; (27)(TC,NP)=Update_CT(vCL,j,NP,TC,TP)   ; (28)NG←NG-NP (29) [BTC, vCL]=Call LBA(vCL)   ;The root of the MST is selected at sensor nodevc that is the closest to the location of the BS. We set the root close to the BS in order to select CLs as close as possible to each other and close to the BS initial position.The next task of AT-BHA is to find the farthest node,vf, from the BS position in the partition tree. The routing path between the farthest node and root of TP is referred to as R(vf,vc) and it is used to find the candidate CL node. We assume the set of nodes in R is sorted in decreasing order according to the number of hops to vc. In the case of the number of nodes in the routing path being less than h, then the root of the TP tree is selected as vCL. While the node at h hop away from the vf is selected as vCL if the route length is higher than h.The Breath-First-Search (BFS) algorithm with bounded hop count is used to find the Minimum Spanning Tree (MST) rooted at the CL. A partial BFS tree is constructed hop by hop, and the expansion continues until all nodes withinh hops are explored. The set of sensors contained in the partial jth tree is referred to as TCj,h. The set of the nodes covered in the jth CT is removed from the set of partition tree nodes, NP.In this algorithm, we propose to find the next CT adjacent to the last constructed tree in order to avoid partitioned node between the CTs. The partitioned node increases the tour length since the BS has to visit the node for data collection. To find an adjacent tree to thejth tree, the algorithm calculates the ratio α=d(NP,vc)/d(NP,vCL). The d(v1,v2) represents Euclidean distance between vertices v1 and v2. The node from NP with maximum α is selected and referred to as nf. This node represents the farthest node to BS and closest to the TCj,h. The closest node to the BS that is within the distance hrβ from nf is selected as the second vCL, where r is the sensor transmission range and β between -1 and 1. The value rβ represents the hop progress and its ranges from -r to r depend on the network node density [25]. New MST is constructed rooted at vCL to find set of nodes within h hops.The number of nodes within each tree and the position of the CL nodes have a signification effect on the tour length. When the CT consists of many nodes, a less number of CLs are required and the tour length decreases. In addition, the tour length is also decreased as the selected CLs are close to the BS. To improve the tree size and location ofvCL, the Update_CT algorithm is proposed in Algorithm 2.Algorithm 2:Update_CT.
Input: vCL, j, NP, TC, TP, τ Output: TC,NP (1)if  vCL  is the first time for check  then (2)NCL←TCj,h; (3)if  |NCL|/d(vCL,vc)≤τ  then (4)Find the routing path R(vCL,vc) using partition tree TP; (5)if  h≥RvCL,vc  then (6)NP←NP∪R(vCL,vc); (7)vCL←vc; (8)else (9) Find vertex vh from R(vCL,vc) at h hops from vCL; (10)NP←NP∪R(vCL,vh); (11)vCL←vh; (12) (13)Find an MST TCj,h(vCL,NP); /∗ Update the j-th tree∗/   ; (14)NP←NP-TCj,h; (15) Return(TC,NP)In the Update_CT algorithm, the ratio of the number of tree nodes to the distance between thevCL and vc is used as a measure of tree usefulness. A threshold value, τ, is used to decide the updating of the CT. The range of τ is (1/d(LBS,NF),n/d(LBS,vBS)), where n is the network nodes, and LBS, vBS, and NF are, respectively, the position of BS, the closest node to the BS, and the farthest node to the BS.In order to avoid infinite looping, the algorithm first checks whether the CT is previously updated since in some cases it is impossible to update the tree because of limited number of nodes. In the case the CT needs to update, the routing path betweenvCL and vc is used to select a new CL node. NP is updated by including the set of CT nodes and the set of routing nodes to the selected vCL. Finally, the updated CT is constructed and returns the updated CT and NP to the AT-BHA algorithm. The AT-BHA algorithm continues until all the network nodes are associated with CTs.


## 3.2. Farthest Node First-Bounded Hop Algorithm (FNF-BHA)

This algorithm constructs CTs to include the farthest nodes to the BS. The FNF-BHA starts similar to AT-BHA by finding the nodes closest to the position of the BS and construction partitions trees. It then finds the route of data packets tovf in the current partition tree to determine the CL node. The nodes involved in the data relay between vf and the collection node are critical for data gathering from vf. In the case of any of the relay node participating in another CT, the BS has to visit vf for data collection increasing the tour length. Therefore, in this case, the algorithm first identifies and then removes all the relay nodes from other CTs by calling the Node Removal Algorithm (NRA) as shown in Algorithm 3. The set of removed nodes is used in the construction of new CTs at the next iteration.Algorithm 3:The Farthest Node First-Bounded Hop Algorithm (FNF-BHA).
Input: A sensor network G(V,E), hop cout h Output: Set of CL nodes vCL, BTC (1)NG←V   ;/∗set of nodes in the network∗/   ; (2)while  NG  is not empty  do (3)Find the closest vertex vc to the BS position from NG; (4)Find an MST Tp that covers vertices from NG; (5)NP←TP; set of nodes in partition tree Tp   ; (6)while  NP  is not empty  do (7)Flag ← false   ; /∗no node need to remove from any tree   ; (8)Find the farthest leave vertex vf to vc on Tp; (9)Find the routing path R(vf,vc); (10)if  h≥|R(vf,vc)|  then (11)vCL←vc; (12)else (13)vCL← vertex from R(vf,vc) at h hops from vf; (14)Nr← set of nodes in R(vf,vcL) not in NP; (15)if  Nr  is not empty  then (16)Flag ← true   ; (17)Nrm= NRA(Nr,NP); /∗ call Node Removal Algorithm ∗/ N P ← N P ∪ N r m; (18)if  Flag= false  then (19)if  vCL  selected as  CL  then (20)j=index of tree rooted on vCL; (21)NP←NP∪TCj,h;; (22)else (23) select vCL as Collection Location   ; (24)j=j+1; (25) (26)Find an MST TCj,h(vCL,NP); (27)NP←NP-TCj,h; (28)NG←NG-NP; (29) [vCL,BTC]=Call LBA(vCL)   ;The algorithm tests whether the CL node is already selected as CL of another tree. In this rare case, the set of CT nodes are merged with that tree and new CT is constructed. The new tree includes all the nodes of previous CT in addition tovf, since all the relay nodes are available in the set of nodes, whereas, if the CL node is not selected, a new CT is constructed with a new tree index to include vf. The algorithm is terminated when all the partitioned tree nodes are covered.We now describe NRA algorithm in more detail. The pseudocode is given in Algorithm4. In order to remove the set of nodes in Nr from the CTs, the tree index of each node needs to be found first. The set of nodes that need to be removed from each CT are identified and removed. A new CT is reconstructed after node removal. In some cases, some of the tree nodes, No, are partitioned, since the removed nodes provide a relay path for them. No may be covered by other CTs. Therefore, all the CTs are reconstructed considering No. If a node is associated with CT, the node is removed from No. The algorithm continues until all the nodes in Nr are removed from the CTs.Algorithm 4:Node Removal Algorithm (NRA).
Input: A sensor network G(V,E), hop cout h, Nr, NP Output:  Nr, TC (1)IX← set of tree index of all CTs   ; (2)IXrt← set of tree index of all Nr nodes   ; (3)Nrm←ϕ; (4)No←ϕ; (5)for  each  j  in  IXrt  do (6)Nrt←Nr∩TCj,h∗/ Set of nodes to remove from the j-th tree ∗/  ; (7)Nnt←TCj,h-Nrt;∗/ Set of node of the j-th tree after node removel ∗/   ; (8)get vCL from tree j; (9)Find an MST TCj,h(vCL,Nnt); (10)NP←Nnt-TCj,h;∗/ Set of partitioned nodes ∗/   ; (11)No←No∪NP; (12)if  Nois not empty  then (13)for  each  tree  indexk  in  IX  do (14) get vCL for tree k; (15)nt←TCk,h; (16)nset←TCk,h∪No; (17) Find an MST TCk,h(vCL,nset); (18)Ndif←TCk,h-nt; (19)No←No-Ndif; (20)Nrm←Nrm∪Nrt∪No; (21) Return(Nrm)   ;


## 3.3. Load Balancing and Further Improvement

The proposed algorithms AT-BHA and FNF-BHA can be further improved by balancing the number of nodes in the CTs. The proposed algorithms find the set of CL nodes to collect data from sensor nodes withinh hops. However, there are large differences between the number of nodes in the CTs. In particular, the first constructed tree covers the maximum number of nodes, while the last tree covers only the remaining set of nodes.Thus, we proposed the load balanced algorithm (LBA) with the pseudocode given in Algorithm5. First, the algorithm balanced the number of nodes for each CT using the CT balanced algorithm (CTBA) shown in Algorithm 6. The CTBA first sorts the CTs in increasing order according to the number of nodes in order to start constructing the CT with the minimum number of nodes. The algorithm gradually constructs all the CTs by finding the nodes with one hop from the CL nodes. Then the number of nodes in the CTs increases with the hop count. In some cases, some nodes does not associate to any tree since they are partitioned as the relaying nodes are associated to other CTs. Finally, the LBA returns the balanced CTs (BTC) and partitioned nodes (PN). When there is no PN the algorithm finalizes the BTC and no further process is required. However, a new set of vCL needs to be selected from the PN for data collection. This is achieved by finding the farthest node vf to the BS from PN. The routing path between vf and closest node to the BS is used to find the vCL at h hops. A new CT is constructed and rooted at vCL to cover PN nodes. Finally, the algorithm rebalanced the load by calling the LBA. The LBA is terminated when there is no partition node in the PN.Algorithm 5:Load balanced algorithm (LBA).
Input: A sensor network G(V,E), hop cout h, tree index j, TC Output: Set of CL nodes CL, BTC (1) [BTC,PN]=Call CTBA(G, TC)   ; (2)while  PN  is not empty  do (3)TC=BTC; copy all the CTs to TC; (4)j← number of trees in TC; (5)Find the farthest leave vertex vf from PN using TP; (6)Find the routing path R(vf,vc); (7)if  h≥|R(vf,vc)|   then (8)vCL←vc; (9)Rn←|R(vf,vc)|; (10)else (11)vCL← vertex from R(vf,vc) at h hops from vf; (12)Rn← nodes at h hops from Vf; (13)PN←PN∪Rn; (14)j=j+1; (15) Find an MST TCj,h(vCL,PN); (16)PN←PN-TCj,h; (17) [BTC,PN]=Call CTBA(G, TC)   ; (18) Return(CL, BTC)   ;Algorithm 6:CT balanced algorithm (CTBA).
Input: A sensor network G(V;E), Set of CTs TCj,h, hop count h Output: set of balanced CTs BTCj,h, Remain Nodes PN (1)K← number of CL nodes   ; (2)NG←V;/∗ set of nodes in the network ∗/   ; (3)NGB←NG; (4)BTCj,hc{j=1:K,hc=1:h}←ϕ; (5) SortTCj trees in increasing order according to the number of nodes in each tree   ; (6)NGB=NG-vCL // remove CL nodes from testing nodes   ; (7)for  hc= 1 to h  do (8)for  each  vCL  do (9)j=j+1; (10)if  hc>1  then (11)NGB=NGB∪BTCj,hc-1; (12)Find an MST BTCj,hc(vCL,NGB); (13)NGB=NGB-BTCj,hc /∗ remove tree nodes from testing nodes ∗/   ; (14)PN=NG-NGB; (15) Return(BTC,PN)   ;


## 4. Performance Evaluation

In this section, we evaluate the performance of the proposed algorithms through simulations. We assume that sensor nodes in the network are randomly deployed with uniform distribution in a400m×400m square sensing field. Each sensor node has a transmission range of r=25m. We first vary the hop count to evaluate the performance of the algorithms. We also vary the number of nodes in the network to emulate the change in the node degree. The node degree is used as a metric of node density. We compare our algorithms with the SPT-DGA algorithm proposed in [5]. For the AT-BHA, we set β=0.5 and τ=0.1. For each instance of deployment, the network performance metrics are calculated, and the result is the average over 500 instances for each node degree and hop count.We adopt the nearest neighbor algorithm [26] in our simulation for the travelling salesman problem to determine the tour of the mobile BS. In order to calculate the energy consumption of CL in transmitting CT sensors data to the BS on wireless communication per time unit, we adopt the energy model [2], ECCL(CL)=ra·LR·(NTCL+1)·Et, where ECCL(CL) is the energy consumption of CL, ra is data generation rate, LR is the length of single data reading, and NTCL is the number of sensors the CL node has to forward their data to the BS. Et is the amount of power consumed by transmitting a unit-length of data. Et can be represented by Et=α1+α2rγ, where α1 is a constant that represents the energy consumption to run the transmitter circuitry which is negligibly small, α2 is a constant that represents the transmitter amplifier, and r is the transmission range. The exponent γ is determined by the field measurements, which is typically a constant between 2 and 4. In this simulation we assume ra=1Kbps, LR=1Kb, α1=0, α2=150nJ/bit/m2, and γ=2.


### 4.1. Varying Hop Count

We first study the effect of changing the hop count on the network performance. Figure1 plots the performance of our algorithms and the SPT-DGA in terms of tour length and hop count, h. When h is small, the number of nodes within each CT is small and thus the number of CLs increased, which increases the length of the mobile BS. The result also shows that the tour length in the FNF-BHA algorithm is the shortest since the FNF-BHA algorithm considered the farthest nodes.Figure 1
The tour length of the mobile BS with the hop count for the SPT-DGA, FNF-BHA and AT-BHA algorithms, ford=12.The maximum number of nodes in the CTs with the number of hops is shown in Figure2. The result shows that as the hop count increases the number of nodes in the CTs increased. This makes sense as increasing the number of hops added extra nodes to the CTs. The result also shows that the number of nodes in the CTs constructed by SPT-DGA algorithm is always less than that in our algorithms.Figure 2
The maximum number of nodes in the CT with the hop count for the SPT-DGA, FNF-BHA and AT-BHA algorithms, ford=12.We also study the number of CLs with the hop count as shown in Figure3. The result shows that the numbers of CLs in our algorithms are significantly less than that in SPT-DGA; this is because the proposed algorithms try to construct CTs with maximum number of nodes by finding routes to the partition nodes and adjacent CTs.Figure 3
The number of CLs with the hop count for the SPT-DGA, FNF-BHA and AT-BHA algorithms, ford=12.The CL consumes more energy than any other network nodes since it has to forward the sensing data of the CT to the BS. Figure4 illustrates the maximum energy consumption of CL for forwarding sensing data of a single sensor node by dividing the total energy consumption of the CL to the number of sensors in the CT. The result shows that the energy consumption decreases with the hop count as the number of nodes in the CT increased with hop count. The result also shows that the energy consumption of the CL at FNF-BHC algorithm is lower that other algorithms since the FNF-BHC algorithm constructed CTs with the maximum number of nodes.Figure 4
The maximum energy consumption of the CL sensor node for forwarding sensing data of single sensor node with the hop count for the SPT-DGA, FNF-BHA, and AT-BHA algorithms, ford=12.The maximum distance between the CL and the farthest sensor nodes is examined in Figure5. The CLs selected by the AT-BHA are the closest to the sensor nodes since the AT-BHA algorithm constructed adjacent trees using hop progress βr rather than dealing with the farthest nodes.Figure 5
The maximum distance between the CL and the farthest sensor node with the hop count for the SPT-DGA, FNF-BHA, and AT-BHA algorithms, ford=12.To better understand the results, we give examples in Figures6, 7, and 8 where 245 sensors are scattered over 200m×200m field (d=12) with the initial position of data BS located at the center of the area. The h is set to 4, which means that it is required for each sensor to forward its data to the CL within four hops. The figures also show the construction of CTs rooted at CLs for each algorithm.Figure 6
An example illustrates the CLs and CTs constructed using SPT-DGA for a network of244 sensors. The tour length is equal to 599.2 m with 15 CL nodes, h=4 and d=12.Figure 7
An example illustrates the CLs and CTs constructed using AT-BHA for a network of244 sensors. The tour length is equal to 464.6 m with 6 CL nodes, h=4 and d=12.Figure 8
An example illustrates the CLs and CTs constructed using FNF-BHA for a network of244 sensors. The tour length is equal to 360.5 m with 5 CL nodes, h=4 and d=12.The SPT-DGA constructs 15 routing trees for data collection as shown in Figure6. The CLs are selected very close to the center of the sensing area in order to minimize the tour length. However, for the same sensors positions, the AT-BHA and FNF-BHA constructed 6 and 5 routing trees, respectively. The position of the CLs selected in the FNF-BHA is closer to the center of the sensing field than that in AT-BHA.


### 4.2. Varying Node Degree

We then vary the node degree in the network by varying the number of network nodes according ton=d∗A/(π∗r2), where A is the network area and r is the node transmission range.To study the effect of the node degree on the tour length, the tour of the mobile BS is calculated using the nearest neighbor algorithm (as shown in Figure9 for our algorithms and the SPT-DGA algorithm). It can be seen that, under different d, the tour length for AT-BHC and FNF-BHA is shorter than that for the SPT-DGA algorithm. This is because the FNF-BHC selects the minimum number of CLs considering the farthest nodes to the position of the BS while the SPT-DGA selects more CLs, which increases the length of mobile BS tour. The result also shows that the tour length slightly increases with the node degree in SPT-DGA. However, increasing the node degree reduced the tour length for the AT-BHA and FNF-BHA since that improves network connectivity and finding routing paths to the farthest nodes. This reduces the number of CLs, as shown in Figure 10.Figure 9
The tour length of the mobile BS with the node degree for the SPT-DGA, AT-BHA and FNF-BHA algorithms, forh=4.Figure 10
The number of CLs with the node degree for the SPT-DGA, AT-BHA and FNF-BHA algorithms, forh=4.Figure11 illustrates the maximum number of nodes in the CTs with the node degree as a function of h. The result shows that the number of nodes increases with the node degree since that increases the number of neighbors.Figure 11
The maximum number of nodes with the node degree for the SPT-DGA, AT-BHA, and FNF-BHA algorithms, forh=4.Figure12 shows the maximum energy consumption of the CL for forwarding sensing data of a single sensor node to the BS. The result shows that the energy consumption slightly decreases with the node degree. In addition, the CL at FNF-BHA consumes less energy than other algorithms since the number of nodes at the CT of the FNF-BHA is more than the number of nodes at the CTs of SPT-DGA and AT-BHA as shown in Figure 11.Figure 12
The maximum energy consumption of the CL sensor node for forwarding sensing data of single sensor node with the node degree for the SPT-DGA, AT-BHA, and FNF-BHA algorithms, forh=4.We study the distance the packet travels to reach the BS by calculating the distance between the sensor nodes. The distance between the farthest sensor node and the CL is shown in Figure13. The result shows that the maximum distance is higher in SPT-DGA and FNF-BHA than in AT-BHA. This is because the expansion of CTs in AT-BHA depends on the settings of β and hop count, while it depends on hop count only for the SPT-DGA and FNF-BHA algorithms.Figure 13
The maximum distance between the CL and sensor nodes with the node degree for the SPT-DGA, AT-BHA, and FNF-BHA algorithms, forh=4.Finally, we study the effect of load balanced algorithm on the distribution of the number of sensor nodes in the CTs. Figure14 shows the histogram of the number of nodes in the CTs before and after the execution of the load balanced algorithm. The result shows that there is high occurrence of trees, with the number of nodes less than 20 nodes for the unbalanced FNF-BHA. However, the number of nodes is very well distributed for the balanced FNF-BHA.Figure 14
Comparison between the number of nodes at balanced and unbalanced CTs for FNF-BHA algorithm withh=4 and d=10.


## 4.1. Varying Hop Count

We first study the effect of changing the hop count on the network performance. Figure1 plots the performance of our algorithms and the SPT-DGA in terms of tour length and hop count, h. When h is small, the number of nodes within each CT is small and thus the number of CLs increased, which increases the length of the mobile BS. The result also shows that the tour length in the FNF-BHA algorithm is the shortest since the FNF-BHA algorithm considered the farthest nodes.Figure 1
The tour length of the mobile BS with the hop count for the SPT-DGA, FNF-BHA and AT-BHA algorithms, ford=12.The maximum number of nodes in the CTs with the number of hops is shown in Figure2. The result shows that as the hop count increases the number of nodes in the CTs increased. This makes sense as increasing the number of hops added extra nodes to the CTs. The result also shows that the number of nodes in the CTs constructed by SPT-DGA algorithm is always less than that in our algorithms.Figure 2
The maximum number of nodes in the CT with the hop count for the SPT-DGA, FNF-BHA and AT-BHA algorithms, ford=12.We also study the number of CLs with the hop count as shown in Figure3. The result shows that the numbers of CLs in our algorithms are significantly less than that in SPT-DGA; this is because the proposed algorithms try to construct CTs with maximum number of nodes by finding routes to the partition nodes and adjacent CTs.Figure 3
The number of CLs with the hop count for the SPT-DGA, FNF-BHA and AT-BHA algorithms, ford=12.The CL consumes more energy than any other network nodes since it has to forward the sensing data of the CT to the BS. Figure4 illustrates the maximum energy consumption of CL for forwarding sensing data of a single sensor node by dividing the total energy consumption of the CL to the number of sensors in the CT. The result shows that the energy consumption decreases with the hop count as the number of nodes in the CT increased with hop count. The result also shows that the energy consumption of the CL at FNF-BHC algorithm is lower that other algorithms since the FNF-BHC algorithm constructed CTs with the maximum number of nodes.Figure 4
The maximum energy consumption of the CL sensor node for forwarding sensing data of single sensor node with the hop count for the SPT-DGA, FNF-BHA, and AT-BHA algorithms, ford=12.The maximum distance between the CL and the farthest sensor nodes is examined in Figure5. The CLs selected by the AT-BHA are the closest to the sensor nodes since the AT-BHA algorithm constructed adjacent trees using hop progress βr rather than dealing with the farthest nodes.Figure 5
The maximum distance between the CL and the farthest sensor node with the hop count for the SPT-DGA, FNF-BHA, and AT-BHA algorithms, ford=12.To better understand the results, we give examples in Figures6, 7, and 8 where 245 sensors are scattered over 200m×200m field (d=12) with the initial position of data BS located at the center of the area. The h is set to 4, which means that it is required for each sensor to forward its data to the CL within four hops. The figures also show the construction of CTs rooted at CLs for each algorithm.Figure 6
An example illustrates the CLs and CTs constructed using SPT-DGA for a network of244 sensors. The tour length is equal to 599.2 m with 15 CL nodes, h=4 and d=12.Figure 7
An example illustrates the CLs and CTs constructed using AT-BHA for a network of244 sensors. The tour length is equal to 464.6 m with 6 CL nodes, h=4 and d=12.Figure 8
An example illustrates the CLs and CTs constructed using FNF-BHA for a network of244 sensors. The tour length is equal to 360.5 m with 5 CL nodes, h=4 and d=12.The SPT-DGA constructs 15 routing trees for data collection as shown in Figure6. The CLs are selected very close to the center of the sensing area in order to minimize the tour length. However, for the same sensors positions, the AT-BHA and FNF-BHA constructed 6 and 5 routing trees, respectively. The position of the CLs selected in the FNF-BHA is closer to the center of the sensing field than that in AT-BHA.


## 4.2. Varying Node Degree

We then vary the node degree in the network by varying the number of network nodes according ton=d∗A/(π∗r2), where A is the network area and r is the node transmission range.To study the effect of the node degree on the tour length, the tour of the mobile BS is calculated using the nearest neighbor algorithm (as shown in Figure9 for our algorithms and the SPT-DGA algorithm). It can be seen that, under different d, the tour length for AT-BHC and FNF-BHA is shorter than that for the SPT-DGA algorithm. This is because the FNF-BHC selects the minimum number of CLs considering the farthest nodes to the position of the BS while the SPT-DGA selects more CLs, which increases the length of mobile BS tour. The result also shows that the tour length slightly increases with the node degree in SPT-DGA. However, increasing the node degree reduced the tour length for the AT-BHA and FNF-BHA since that improves network connectivity and finding routing paths to the farthest nodes. This reduces the number of CLs, as shown in Figure 10.Figure 9
The tour length of the mobile BS with the node degree for the SPT-DGA, AT-BHA and FNF-BHA algorithms, forh=4.Figure 10
The number of CLs with the node degree for the SPT-DGA, AT-BHA and FNF-BHA algorithms, forh=4.Figure11 illustrates the maximum number of nodes in the CTs with the node degree as a function of h. The result shows that the number of nodes increases with the node degree since that increases the number of neighbors.Figure 11
The maximum number of nodes with the node degree for the SPT-DGA, AT-BHA, and FNF-BHA algorithms, forh=4.Figure12 shows the maximum energy consumption of the CL for forwarding sensing data of a single sensor node to the BS. The result shows that the energy consumption slightly decreases with the node degree. In addition, the CL at FNF-BHA consumes less energy than other algorithms since the number of nodes at the CT of the FNF-BHA is more than the number of nodes at the CTs of SPT-DGA and AT-BHA as shown in Figure 11.Figure 12
The maximum energy consumption of the CL sensor node for forwarding sensing data of single sensor node with the node degree for the SPT-DGA, AT-BHA, and FNF-BHA algorithms, forh=4.We study the distance the packet travels to reach the BS by calculating the distance between the sensor nodes. The distance between the farthest sensor node and the CL is shown in Figure13. The result shows that the maximum distance is higher in SPT-DGA and FNF-BHA than in AT-BHA. This is because the expansion of CTs in AT-BHA depends on the settings of β and hop count, while it depends on hop count only for the SPT-DGA and FNF-BHA algorithms.Figure 13
The maximum distance between the CL and sensor nodes with the node degree for the SPT-DGA, AT-BHA, and FNF-BHA algorithms, forh=4.Finally, we study the effect of load balanced algorithm on the distribution of the number of sensor nodes in the CTs. Figure14 shows the histogram of the number of nodes in the CTs before and after the execution of the load balanced algorithm. The result shows that there is high occurrence of trees, with the number of nodes less than 20 nodes for the unbalanced FNF-BHA. However, the number of nodes is very well distributed for the balanced FNF-BHA.Figure 14
Comparison between the number of nodes at balanced and unbalanced CTs for FNF-BHA algorithm withh=4 and d=10.


## 5. Conclusion

In this paper, we dealt with the problem of data gathering in the mobile BS environment. We studied the trade-off between the relay hop count of sensor nodes and the tour length of the mobile BS. Two heuristic algorithms, AT-BHA and FNF-BHA, are proposed towards finding the shortest tour length for the mobile BS subject to bounded hop count. The AT-BHA selects adjacent CTs during tree construction to avoid partitioned nodes that increased the tour length. The FNF-BHA uses the farthest nodes from the BS in the construction of the CTs. Extensive simulations have been carried out to validate the efficiency of the proposed algorithms against SPT-DGA. The experimental results demonstrated that the proposed algorithms outperform the SPT-DGA significantly in terms of minimizing the BS tour length.



---

*Source: 3929876-2019-02-12.xml*