# An Energy Efficient Data Gathering in Dense Mobile Wireless Sensor Networks

Authors: R. Velmani; B. Kaarthick
Journal: ISRN Sensor Networks
 (2014)

---

## Abstract

Amidst of the growing impact of wireless sensor networks (WSNs) on real world applications, numerous schemes have been proposed for collecting data on multipath routing, tree, clustering, and cluster tree. Effectiveness of WSNs only depends on the data collection schemes. Existing methods cannot provide a guaranteed reliable network about mobility, traffic, and end-to-end connection, respectively. To mitigate such kind of problems, a simple and effective scheme is proposed, which is named as cluster independent data collection tree (CIDT). After the cluster head election and cluster formation, CIDT constructs a data collection tree (DCT) based on the cluster head location. In DCT, data collection node (DCN) does not participate in sensing, which is simply collecting the data packet from the cluster head and delivering it into sink. CIDT minimizes the energy exploitation, end-to-end delay and traffic of cluster head due to transfer of data with DCT. CIDT provides less complexity involved in creating a tree structure, which maintains the energy consumption of cluster head that helps to reduce the frequent cluster formation and maintain a cluster for considerable amount of time. The simulation results show that CIDT provides better QoS in terms of energy consumption, throughput, end-to-end delay, and network lifetime for mobility-based WSNs.


---

## Body

## 1. Introduction

WSNs have recently come into prominence because they hold potential to revolutionize many segments of our economical life, environmental monitoring, health care applications, infrastructure protection, context-aware computing, and battlefield awareness [1]. The strength of WSNs lies in their flexibility, energy consumption, mobility, and scalability. The number of sensors capability and their organized fashion made wireless sensor communication first option to utilize them in remote or hazardous environments. The ultimate goal of such WSNs is often to deliver the sensing data from sensor nodes to sink node and then conduct further analysis at the sink node [2]. To perform such tasks effectively, several network routing protocols have been proposed mainly for data collection.Topology management plays a vital role in minimizing various constraints such as limited energy, computational resource crisis, latency, and quality of communication. Now, the transmission distance between the sensor nodes is responsible for energy consumption. Power loss is always directly proportional to the distancePloss=dρ, where d is the distance between sensor nodes, ρ is the environmental fading factor, ρ=2 for free space fading, and ρ=4 for multipath fading [3]. The topology inherently defines the types of routing path as broadcast or unicast and it determines the size, type of packets, and other overheads. Choosing a right topology helps to reduce the communication overhead and energy conservation. An efficient topology ensures that neighbors are at a minimal distance and reduces the probability of a packet being lost between sensor nodes. An efficient topology management may diminish the long range communication within a network, communication failure and improves the network lifetime.In addition, topologies in WSNs define the dimension of the sensor node group and managing the addition of new members as well as dealing with members who left the group. By considering such aspects, the topology may provide an efficient data collection with low energy utilization and form superior WSN. The existing WSNs topologies are flat, tree, cluster, cluster tree, and chain. Based on the nature of network, different kinds of topologies are followed to gain the maximum data collection efficiency. This paper deals with an existing data collection topology and the proposed logical topology called DCT. It overcomes the existing limitations such as network lifetime and minimizes the energy consumption with effective data collection [4].


## 2. Related Work

Network topology determines the overall efficiency of the WSNs. Based on the data gathering and dissemination applications, various types of logical topologies are defined into (i) flat topology, (ii) cluster based topology, (iii) chain based topology, (iv) tree based topology, (v) cluster tree topology.


### 2.1. Flat/Unstructured Topology (FT)

FT/UT is a very simple method to collect the data for the sink [5]. FT is used in the case of no topology or the absence of any defined topology shown in Figure 1(a) (i.e., flooding and gossiping). Here, each sensor node plays an equal role to form a network. FT construction is a costly operation. It does not bother about the energy constraints which lead to the implosion and overlapping problems [6]. For example, sensor protocols for information via negotiation (SPIN), directed diffusion, energy-aware routing, rumor routing, gradient based routing (GBR), constrained anisotropic diffusion routing (CADR), and cougar and active query forwarding in sensor networks (ACQUIRE) [7–14].(a) Flat topology, (b) cluster based topology.
(a)
(b)


### 2.2. Chain Topology (CT)

The CT constructs a transmission chain to connect the deployed sensor nodes. A node is selected in the chain to act as leader of chain. All the sensor nodes can communicate with each other along the chain. Excessive delay for distant nodes on the chain is the main demerits of this topology (i.e., increasing the length of the chain causes excessive delay where the leaf nodes collected data to reach the leader). When the sensor nodes have high mobility, it leads to the link break problems and affects the network performance. For example, Greedy algorithm, minimum transmission energy (MTE), power efficient gathering in sensor information systems (PEGASIS), chain oriented sensor network (COSEN), and chain routing with even energy consumption (CREEC) [15–17].


### 2.3. Cluster Based Topology (CBT)

CBT has been widely used in WSNs for data gathering, data dissemination, and target tracking. Clustering is a proficient method for specific applications, which requires scalability to hundreds or thousands of nodes (i.e., widely used in dense WSNs) shown in Figure1(b). Scalability in this context implies the need for load balancing, proficient resource exploitation, and data aggregation. In clustering, cluster head election is an important task. Here, the cluster head election is done by various methods like distributed (i.e., cluster head can be elected with probabilistic, residual energy, random method, and election phase) and centralized (i.e., cluster head have been assigned with nonprobabilistic methods by sink or base station) election [18, 19].After the cluster head election, all the cluster heads forward the data to the base station with direct hopping (cluster head directly connected with base station) or multihopping (cluster head to cluster head communication) techniques. For mobility-based environments, frequent changes of cluster head and multihop techniques cannot offer a guaranteed data transmission rate. It diminishes the performance of the entire network. For example, low energy adaptive clustering hierarchy (LEACH), hybrid energy efficient distributed clustering (HEED), base-station controlled dynamic clustering protocol (BCDCP), concentric clustering scheme (CCS), energy aware routing protocol (EAR), hierarchical geographic multicast routing (HGMR), cluster head gateway switch routing (CGSR), and mobility-based clustering protocol (MBC) [20–26].


### 2.4. Tree Based Topology (TBT)

In TBT, all the deployed sensor nodes construct a logical tree. Generally, TBT works with DFS (depth first search) or BFS (breadth first search) method [2]. Here, the entire data packet passes from leaf node to the parent nodes. Likewise, data flow from all sensor nodes to the sink is carried out. Constructing a logical tree avoids packet flooding. It uses unicast instead of broadcast, as the flooding is not necessary for data communication. Therefore, tree topology consumes less power than flat topology. When compared with a few basic clustering protocol, tree topology proves to be much more effective on energy utilization [27]. Tree formation for the whole network is a time consuming and costly operation. It cannot tolerate with node failures and power consumption is uneven across the network. For avoiding the interference problem, different access methods are chosen. Otherwise, it causes delay in sending the data packet from leaf nodes to root node, for example, minimum spanning tree (MST), tree based data collection scheme (TBDCS), and efficient convergecast tree (ECT) [28–30].


### 2.5. Cluster Tree Topology (CTT)

CTT contains cluster and tree topology formation process shown in Figure2. The network design starts with a special node called designated device (DD). It acts as a cluster head with greater transmission power and receiver sensitivity. The beacon signal contains NetID, CID and NID nodes are added to the DD. Whenever, the node receives a beacon from a neighbor node, which sends a CONNECT REQUEST to DD. The DD acknowledges to the corresponding node with Connect Response and the cluster tree formed. Here, the creation of such topology with node id is a tedious process. Then, the special nodes (DD) should be initiated to make cluster tree [31], for example, ZigBee, 6LoWPAN. The main objective of cluster tree is increasing the network capacity, minimizing the energy consumption and end-to-end delay. But, the effectiveness of cluster tree is based on the network parameters like scalability, data rate, cluster dimension (number of clusters and cluster members for each cluster), tree intensity (number of layers), RSS (received signal strength) and mobility (node position, velocity, and direction), for example, cluster tree data gathering algorithm (CTDGA) [32].Figure 2
Cluster tree topology.


### 2.6. Mobility Model

The mobility model is designed to describe the location, velocity, and direction change over a time of mobile sensor nodes. The random waypoint model (RWM) is used in mobility management schemes (e.g., ad hoc networks and sensor networks) [33]. The node travels from a starting coordinate to a random ending coordinate with a randomly generated constant velocity. The velocity is picked from [0,Vmax⁡] interval. When a sensor node reaches the destination point, the node waits for a Tpause time earlier than arriving at the next destination [34].


## 2.1. Flat/Unstructured Topology (FT)

FT/UT is a very simple method to collect the data for the sink [5]. FT is used in the case of no topology or the absence of any defined topology shown in Figure 1(a) (i.e., flooding and gossiping). Here, each sensor node plays an equal role to form a network. FT construction is a costly operation. It does not bother about the energy constraints which lead to the implosion and overlapping problems [6]. For example, sensor protocols for information via negotiation (SPIN), directed diffusion, energy-aware routing, rumor routing, gradient based routing (GBR), constrained anisotropic diffusion routing (CADR), and cougar and active query forwarding in sensor networks (ACQUIRE) [7–14].(a) Flat topology, (b) cluster based topology.
(a)
(b)


## 2.2. Chain Topology (CT)

The CT constructs a transmission chain to connect the deployed sensor nodes. A node is selected in the chain to act as leader of chain. All the sensor nodes can communicate with each other along the chain. Excessive delay for distant nodes on the chain is the main demerits of this topology (i.e., increasing the length of the chain causes excessive delay where the leaf nodes collected data to reach the leader). When the sensor nodes have high mobility, it leads to the link break problems and affects the network performance. For example, Greedy algorithm, minimum transmission energy (MTE), power efficient gathering in sensor information systems (PEGASIS), chain oriented sensor network (COSEN), and chain routing with even energy consumption (CREEC) [15–17].


## 2.3. Cluster Based Topology (CBT)

CBT has been widely used in WSNs for data gathering, data dissemination, and target tracking. Clustering is a proficient method for specific applications, which requires scalability to hundreds or thousands of nodes (i.e., widely used in dense WSNs) shown in Figure1(b). Scalability in this context implies the need for load balancing, proficient resource exploitation, and data aggregation. In clustering, cluster head election is an important task. Here, the cluster head election is done by various methods like distributed (i.e., cluster head can be elected with probabilistic, residual energy, random method, and election phase) and centralized (i.e., cluster head have been assigned with nonprobabilistic methods by sink or base station) election [18, 19].After the cluster head election, all the cluster heads forward the data to the base station with direct hopping (cluster head directly connected with base station) or multihopping (cluster head to cluster head communication) techniques. For mobility-based environments, frequent changes of cluster head and multihop techniques cannot offer a guaranteed data transmission rate. It diminishes the performance of the entire network. For example, low energy adaptive clustering hierarchy (LEACH), hybrid energy efficient distributed clustering (HEED), base-station controlled dynamic clustering protocol (BCDCP), concentric clustering scheme (CCS), energy aware routing protocol (EAR), hierarchical geographic multicast routing (HGMR), cluster head gateway switch routing (CGSR), and mobility-based clustering protocol (MBC) [20–26].


## 2.4. Tree Based Topology (TBT)

In TBT, all the deployed sensor nodes construct a logical tree. Generally, TBT works with DFS (depth first search) or BFS (breadth first search) method [2]. Here, the entire data packet passes from leaf node to the parent nodes. Likewise, data flow from all sensor nodes to the sink is carried out. Constructing a logical tree avoids packet flooding. It uses unicast instead of broadcast, as the flooding is not necessary for data communication. Therefore, tree topology consumes less power than flat topology. When compared with a few basic clustering protocol, tree topology proves to be much more effective on energy utilization [27]. Tree formation for the whole network is a time consuming and costly operation. It cannot tolerate with node failures and power consumption is uneven across the network. For avoiding the interference problem, different access methods are chosen. Otherwise, it causes delay in sending the data packet from leaf nodes to root node, for example, minimum spanning tree (MST), tree based data collection scheme (TBDCS), and efficient convergecast tree (ECT) [28–30].


## 2.5. Cluster Tree Topology (CTT)

CTT contains cluster and tree topology formation process shown in Figure2. The network design starts with a special node called designated device (DD). It acts as a cluster head with greater transmission power and receiver sensitivity. The beacon signal contains NetID, CID and NID nodes are added to the DD. Whenever, the node receives a beacon from a neighbor node, which sends a CONNECT REQUEST to DD. The DD acknowledges to the corresponding node with Connect Response and the cluster tree formed. Here, the creation of such topology with node id is a tedious process. Then, the special nodes (DD) should be initiated to make cluster tree [31], for example, ZigBee, 6LoWPAN. The main objective of cluster tree is increasing the network capacity, minimizing the energy consumption and end-to-end delay. But, the effectiveness of cluster tree is based on the network parameters like scalability, data rate, cluster dimension (number of clusters and cluster members for each cluster), tree intensity (number of layers), RSS (received signal strength) and mobility (node position, velocity, and direction), for example, cluster tree data gathering algorithm (CTDGA) [32].Figure 2
Cluster tree topology.


## 2.6. Mobility Model

The mobility model is designed to describe the location, velocity, and direction change over a time of mobile sensor nodes. The random waypoint model (RWM) is used in mobility management schemes (e.g., ad hoc networks and sensor networks) [33]. The node travels from a starting coordinate to a random ending coordinate with a randomly generated constant velocity. The velocity is picked from [0,Vmax⁡] interval. When a sensor node reaches the destination point, the node waits for a Tpause time earlier than arriving at the next destination [34].


## 3. Problem Statement

In flat topology, all the sensor nodes directly communicate with the sink or simply forward the data packets to the neighbor nodes. Whenever, the sensor node wants to communicate with a sink, the existing methods have limitation such as delay, data redundancy, and large amount of energy exploitation. Since, it is using flooding, gossiping, direct communication, and so forth. The cluster based data collection suggests better performance with cluster heads. Conversely, the data dissemination from cluster head to cluster head or sink (cluster head to sink communication must be either direct hop or multihop communication) involves reliable stable links, which causes more energy consumption. For mobility-based environments, frequent cluster changes of the sensor node lead to link failure which causes diminishing the network lifetime.CT provides better performance than flat and cluster topology. However, it increases the data collection time than CBT. Since, it must follow the chain route to reach sink, the entire network dies slowly due to the even energy utilization of overall WSN. TBT can save more energy than CBT. It includes several time stamps in order to collect data from leaf to root node. In mobility environment, it leads to link failure, packet drop, and delayed transmissions.CTT offers enhanced performance than FT, CT, CBT, and TBT. The cluster head (DD) selection, maintaining the cluster with stable links for mobile sensor nodes is a costy operation. The above topologies are not feasible and mended adapt to mobile sensor ambiance. To overcome the existing limitations in the above FT, CT, CBT, TBT, and CTT, we propose a novel logical topology for data collection, namely, cluster independent data collection tree (CIDT).Figure3 shows the simple outline of our proposed scheme named into CIDT structure. It is a unique nature of logical scheme, which helps to improve the network lifetime and effective data collection, thereby increasing network lifetime with minimum delay. CIDT is a best hybrid scheme (which utilizes cluster and tree topology) suitable for dense wireless sensor networks than any other logical topology. On mobility-based environments, it provides better performance than other methods.Figure 3
CIDT structure.


## 4. CIDT (Cluster Independent Data Collection Tree)

The CIDT consists of setup phase and steady state phase. In setup phase, cluster formation and tree construction is initiated to identify the optimal path between cluster member and sink. It is denoted in intracluster and DCT communication. DCT construction for single cluster is shown in Figure4.Figure 4
CIDT in single cluster.Now, the cluster head is responsible for the data collection from cluster members and cluster maintenance operations. At first, all the sensor nodes elect ahead to the cluster head and form a cluster. Thereafter, tree formation is initiated, which connects the cluster head and sink. Here, the cluster formation and DCT construction is based on the threshold value, connection time, and RSS. After the setup phase completion, data transmission is initiated in steady state phase. Here, all the cluster members send ahead the data packets to sink based on the optimal path.


### 4.1. CIDT Tree Formation

For a large-scale WSN, numerous number of sensor nodes have been randomly deployed. In this case, the selection of DCN does not affect the data collection of a corresponding cluster. It should have better connection time with the nearest DCN node and cluster head. The DCT formation is based on the location of cluster head, connection time between the cluster head and DCN. After the cluster head election, BS or sink initiates ahead to the DCT formation process. Based on the location of cluster head and connection time, a few numbers of nodes are selected as DCN. Now, the DCN may act as a data collection node and does not participate in sensing. But, it does not belong to any cluster.All the DCN collects the data from cluster head, which aggregate with the corresponding cluster head and then forward to the next DCN. The DCN selection algorithm is executed by sink in order to select the DCN to form an independent tree structure. Figure5 presents the flow chart of DCT construction.Figure 5
Flow chart of DCT construction.Algorithm1 steps:(a)
Initialize the values.(b)
Choose a random TIN (temporary independent node) from sink.(c)
In case, a very first one-hop distance node from the sink is CH. Then, skip to another one-hop NN (Neighbor Node).(d)
Select a one-hop NN as CNI (Current Node Identity) and assign the integrity as TIN.(e)
Now, the one-hop distance (NH, NN) CNI from the sink is considered into TIN and select a better TIN among them.(f)
Select a one-hop distance NN to the CH as PIN from TIN.(g)
In that case, step (c) is not able to find TIN. Then, skip to select a SIN from TIN, which is another one-hop distance NN (Neighbor Node) from CH.(h)
Increment the value of NH and NN for next DCN selection.(i)
Change the integrity of SIN (Selected Independent Node) to FSIN (Finalized and Selected Independent Node).(j)
Choose a FSIN from random TIN.(k)
Let the integrity of FSIN considered as DCN, which is used to construct a DCT link between the sink and cluster head.Algorithm 1:DCT Construction.
DCT (CNI, NH, HC, NN)
inti, j, m, N, NH = 1, HC = 1       (a)
for (i← 1 to N)             (b)
{   if (CNI == CH)
{
NH = NH++            (c)
TIN ← NH            (d)
}
else
{
if (CNI == NN && CNI = CH++ && TIN == CNI)
for (j← 0 to m)          (e)
{
PIN← TIN              (f)
}}
else
{
SIN ← TIN            (g)
NH ← NH++
NN ← NH++           (h)
}
if (PIN == TIN && SIN == TIN && SIN == PIN)
{
FSIN ← SIN           (i)
}
else
{
FSIN ← Random (TIN)        (j)
}
DCN = FSIN
DCT ← DCN           (k)
}The above list represents the algorithm for DCT. Initially sink starts with the one-hop neighbor sensor node to add that particular node to act as a DCN in DCT. The parameters include HC = 1 (hop distance is used to select a one-hop neighbor node from sink to act as a current node identity (CNI)), NH (new hop distance is an additive value, which denotes the current distance of node (CNI) from sink and it is used to finalize the DCN selection). Then, the identified nodes have been stored in temporary structure (TIN). In case, the one-hop distance neighbor node (NN) is found to be CH, one node from the cluster head with HC = 1 is identified as TIN. After finding the NH of the network, starting with the nearest node as cluster head, the node selection is finalized. Then selected nodes are utilized to form the DCT.DCT is a hierarchical tree structure, which covers the entire WSNs. DCN collects the data from the cluster heads and delivers it to sink or BS. Selecting DCN with better connection time and best communication range reduces energy consumption due to long range node to node data transfer. While the sensor nodes are on high mobility, the selected DCN keeps the communication with the cluster head for a longer time and there is no need to update the tree structure. In order to keep the lifetime of whole network in harmony DCN is also newly selected every time when the new cluster heads are elected. New DCN selection also is carried out by sink, which is based on the mobility of the new cluster head.


### 4.2. Intracluster Communication

Considering ambiguous large-scale WSNs, sensor nodes have been densely deployed over the region. During the setup phase, the beacon signal is used to identify the sensor nodes location and position. Once the nearby nodes are identified, random algorithm or election algorithm is used to elect the cluster head. After the cluster head selection, the next phase DCT formation is initiated.In the proposed method, the threshold valueUabn has been calculated in (1) by adding the flag value with the multiplication of factors such as the total number of neighbor nodes, residual energy, and current speed of the sensor node, where FC is the flag (set FC=1 for previous round cluster head and FC=0 for sensor node having a chance to act as current round cluster head based on Uabn), En-current is the current sensor node energy, Vn-current is the current speed of the sensor node, Emax⁡ is the initial energy, and Vmax⁡ is the maximum speed of the sensor node. In order to avoid the election of high mobility node as cluster head, ((Vmax⁡-Vn-current)/(Vmax⁡+Vn-current)) instead of (Vmax⁡/Vn-current) may be considered. The expected number of sensor nodes in each cluster is m=NS/CH. Those nodes having maximum residual energy, maximum number of cluster members, and maximum connection time can be elected as cluster head in (1):
(1)Uabn=(Vmax⁡-Vn-currentVmax⁡+Vn-currentFC+(Nb-currentNmax⁡-Nb-current×Emax⁡-En-currentEmax⁡×Vmax⁡-Vn-currentVmax⁡+Vn-current)).
It is visualized that the 2D network position of the cluster headband sensor node a at time t is characterized in (2) as follows:
(2)Xb=xb+vb*cos⁡⁡θbt;Yb=yb+vb*sin⁡θbtXa=xa+va*cos⁡⁡θat;Ya=ya+va*sin⁡θat,
where (x,y) is the primary node location, v is the speed, θ is the moving path angle between (x,y), and t is the connection time. Then, the subscript (a,b) corresponds to sensor node a and cluster head b, respectively. Let the Rabt be denoted as (3)
(3)Rabt≥((Xb-Xa)2+(Yb-Ya)2)1/2.
At time t=0, each sensor node receives an advertisement message from any one of the cluster heads. Hence, the above 2D network equation (3) is considered and simplified into (4)
(4)Rabt≥((xb-xa)2+(yb-ya)2)1/2ift=0.
Now, ΔRabt,t+s is the difference between Rabt and Rabt+s at time instance t and t+s. Let ΔRabt,t+s be found using (4):
(5)ΔRabt,t+s=Rabt-Rabt+sif(n,s)∈t,s=0,1,2.…n.
However, for ΔRabt,t+s=0, there is no sensor nodes on mobility within a cluster. ΔRabt,t+s is the negative value for sensor nodes in a cluster moving away from the cluster head; ΔRabt,t+s is the positive value cluster head and cluster member moving towards to each other. Now, the RSS (received signal strength) can be calculated at any time instance t and t+n in (6)
(6)RSSabt=RSSab-currentt-RSSab-minRSSabt+s=RSSab-currentt+s-RSSab-min∀s∈t,
whereas RSSab-min is the minimum required threshold value and RSSab-currentt+s is the current threshold value at time instance t. If RSS is a positive value, the cluster members join in an appropriate cluster and communicate with corresponding cluster head. In this case, ΔRSSabt,t+s is the difference between RSSabt and RSSabt+s, which can be found from (6)
(7)ΔRSSabt,t+s=RSSabt-RSSabt+s,
wherever, ΔRSSabt,t+s≤0, cluster member move away from the current position of the cluster head. ΔRSSabt,t+s≥0, both cluster member and cluster head move towards each other from their current position. Gabn is the value assigned to sensor nodea on round, which indicates its robustness for connection with cluster headb. The dimensionless value δG,ζG,ηG, and κCT is a linear combination with constant coefficients between0 and1. The coefficients represent the consequence of each factor and are denoted in (8) as follows:
(8)δG+ζG+ηG+κCT=1.
Therefore, (8) can be originated into Gabn and in (9) represented as
(9)Gabn=(δT×(Emax⁡-Eb-currentEb-current×Nb-current))+(ζT×(1-RSSab-minRSSab-current))+(ηT×(dba-RabtRabt))+(κCT×(Δtabbtcf)),
where Emax⁡ is the initial energy, Eb-current is the cluster head current energy, Nb-current is the number of current cluster members for cluster head b, RSSab-min is the minimum required RSS from a and b, RSSab-current is the current RSS betweena and b, Rabt is the distance betweena andb at any time instance t, dba is the maximum coverage distance betweenb anda, Δtabb is the estimated connection time fora begins its transmission tob, and tcf is the current duration of the data frame forb.


### 4.3. DCT Communication

After the intracluster communication phase, DCT formation phase is initiated. It is based on the threshold value, connection time, and network traffic. DCT makes a communication link between the cluster head and sink. Let it be visualized that the 2D network position of the cluster headb and DCNe orh at timet is
(10)Xb=xb+vb*cos⁡θbt;Yb=yb+vb*sin⁡θbtXe=xe+ve*cos⁡⁡θet;Ye=ye+ve*sin⁡θetXh=xh+vh*cos⁡⁡θht;Yh=yh+vh*sin⁡θht.
On each round, the distance between cluster headb to DCNe andh has been calculated from (10). Let the distance Rbet and Reht be denoted in (11)
(11)Rbet≥((Xb-Xe)2+(Yb-Ye)2)1/2.Reht≥((Xe-Xh)2+(Ye-Yh)2)1/2,0≤t≤n
Let t=0; the distance Rbet and Reht in (11) can be considered as
(12)Rbet≥((xb-xe)2+(yb-ye)2)1/2Reht≥((xe-xh)2+(ye-yh)2)1/2,t=0,∀n∈t.
For any cluster head to DCN or DCN to DCN or sink to DCN communication, the threshold value Uuvp has been calculated in (13) by adding total number of DCN with multiplied factors such as the residual energy, and current speed between cluster head to DCN or DCN to DCN. Let u be considered instead of b (it represents that cluster head or sink or DCN), v as a substitute of e and h (it signifies that DCN):
(13)Uuvp=Hv+(Ev-max-Ev-currentEv-max×Vv-max-Vv-currentVv-max+Vv-current),
where Hv is the count for DCN, Ev-current is the current cluster head energy, Vv-current is the current speed of the cluster head, Ev-max is the initial energy, and Vv-max is the maximum speed of cluster head. Let ΔRuvt,t+n be the diversity with Ruvt and Ruvt+n. At the time instance t and t+n, ΔRuvt,t+n is represented in (14)
(14)ΔRuvt,t+n=Ruvt-Ruvt+n,t=0,1,2…n,∀n∈t.
However, ΔRuvt,t+n=0, both nodes (cluster head and DCN or any two DCN) not in mobility, which is separated in even distance. ΔRuvt,t+n is the negative value for both nodes moving away; ΔRuvt,t+n is the positive value for both nodes moving towards each other. Consequently, the RSS (received signal strength) between any two nodes, at the time instance t and t+n is calculated in (15)
(15)RSSuvt=RSSuv-currentt-RSSuv-minRSSuvt+n=RSSuv-currentt+n-RSSuv-min∀n∈t,
where RSSuv-min is the minimum required threshold value and RSSuv-currentt+n is the current threshold value. If RSSuvt+n is a positive value, then the cluster head or DCN has a likelihood to join with nearest DCN, which can establish the communication with corresponding nodes. ΔRSSuvt,t+n can be found using (15) as follows:
(16)ΔRSSuvt,t+n=RSSuvt-RSSuvt+n,∀n∈t
wherever ΔRSSuvt,t+n≤0, both nodes moving away from their current position. ΔRSSuvt,t+n≥0, both nodes moving towards each other. The dimensionless value δCT,ζCT,ηCT, and κCT is a linear combination with constant coefficients between0 and1. The coefficients represent the consequence of each factor and are denoted as (17)
(17)δCT+ζCT+ηCT+κCT=1.Guvp is the value assigned to all u on each round, which indicates its heftiness for connection with v:
(18)Guvp=(δCT×(Ev-max-Ev-currentEv-current×Nv-current))+(ζCT×(1-RSSuv-minRSSuv-current))+(ηCT×(duv-RuvtRuvt))+(κCT×(ΔtuvvtCTf(Ψ))),
where Ev-max is the initial energy ofv, Ev-current is the current energy of v, Nv-current is the total number of cluster head or DCN connected with v, RSSuv-min is the minimum required RSS to make a connection from u and v, RSSuv-current is the current RSS to establish a connection betweenu and v,duv is the maximum coverage distance between u and v,Ruvt is the distance between u and v at any time instance t, Δtuvv is the estimated connection time for u begins its transmission to v, and tCTf(Ψ) is the current duration of the data frame for v.


### 4.4. Frame Duration

Let us consider the number of current cluster MembersMc and the number of expected cluster members Me can be derived from the following equation (19):
(19)Mc=Me-(Md+Ms)Me=Nc-CH-CTCH;Nc=Nt-Nd,
where Mc is the current cluster member from one cluster, Me is the expected number of cluster member, Md is the number of cluster member dead, Ms is the total number of cluster members on sleep state, Nc is the total number of current sensor nodes, Nt is the total number of sensor nodes over a network, Nd is the number of sensor nodes dead, and CH is the cluster head. Now, the current duration of the data frame tcf from each cluster is denoted in (20)
(20)tcf=LpRb×Mcortcf=LpRb×Me,
where Lp is the data packet length and Rb is the transmission bit rate.


### 4.5. Steady State Phase

On steady state phase, each cluster member and the corresponding cluster head build intracluster communication with each other. Initially, all the cluster members send the sensed data to cluster head in an allocated TDMA time slot. Thereafter, the cluster head aggregates the received data, and then forward the data packet to the DCN. Again, DCN aggregates the data packet from its cluster head and then forward to the sink with DCT. In DCT communication, direct sequence spread spectrum techniques can be used to transfer the data packets from the cluster head to DCN and sink. DCT discovers an optimal path between the cluster head and the sink based on the distance, connection time, threshold value, and residual energy. Based on the optimal path, the entire cluster head forwards the data packets to the nearest DCN. Now, the DCT becomes responsible for forwarding an entire data from the cluster head to sink.


## 4.1. CIDT Tree Formation

For a large-scale WSN, numerous number of sensor nodes have been randomly deployed. In this case, the selection of DCN does not affect the data collection of a corresponding cluster. It should have better connection time with the nearest DCN node and cluster head. The DCT formation is based on the location of cluster head, connection time between the cluster head and DCN. After the cluster head election, BS or sink initiates ahead to the DCT formation process. Based on the location of cluster head and connection time, a few numbers of nodes are selected as DCN. Now, the DCN may act as a data collection node and does not participate in sensing. But, it does not belong to any cluster.All the DCN collects the data from cluster head, which aggregate with the corresponding cluster head and then forward to the next DCN. The DCN selection algorithm is executed by sink in order to select the DCN to form an independent tree structure. Figure5 presents the flow chart of DCT construction.Figure 5
Flow chart of DCT construction.Algorithm1 steps:(a)
Initialize the values.(b)
Choose a random TIN (temporary independent node) from sink.(c)
In case, a very first one-hop distance node from the sink is CH. Then, skip to another one-hop NN (Neighbor Node).(d)
Select a one-hop NN as CNI (Current Node Identity) and assign the integrity as TIN.(e)
Now, the one-hop distance (NH, NN) CNI from the sink is considered into TIN and select a better TIN among them.(f)
Select a one-hop distance NN to the CH as PIN from TIN.(g)
In that case, step (c) is not able to find TIN. Then, skip to select a SIN from TIN, which is another one-hop distance NN (Neighbor Node) from CH.(h)
Increment the value of NH and NN for next DCN selection.(i)
Change the integrity of SIN (Selected Independent Node) to FSIN (Finalized and Selected Independent Node).(j)
Choose a FSIN from random TIN.(k)
Let the integrity of FSIN considered as DCN, which is used to construct a DCT link between the sink and cluster head.Algorithm 1:DCT Construction.
DCT (CNI, NH, HC, NN)
inti, j, m, N, NH = 1, HC = 1       (a)
for (i← 1 to N)             (b)
{   if (CNI == CH)
{
NH = NH++            (c)
TIN ← NH            (d)
}
else
{
if (CNI == NN && CNI = CH++ && TIN == CNI)
for (j← 0 to m)          (e)
{
PIN← TIN              (f)
}}
else
{
SIN ← TIN            (g)
NH ← NH++
NN ← NH++           (h)
}
if (PIN == TIN && SIN == TIN && SIN == PIN)
{
FSIN ← SIN           (i)
}
else
{
FSIN ← Random (TIN)        (j)
}
DCN = FSIN
DCT ← DCN           (k)
}The above list represents the algorithm for DCT. Initially sink starts with the one-hop neighbor sensor node to add that particular node to act as a DCN in DCT. The parameters include HC = 1 (hop distance is used to select a one-hop neighbor node from sink to act as a current node identity (CNI)), NH (new hop distance is an additive value, which denotes the current distance of node (CNI) from sink and it is used to finalize the DCN selection). Then, the identified nodes have been stored in temporary structure (TIN). In case, the one-hop distance neighbor node (NN) is found to be CH, one node from the cluster head with HC = 1 is identified as TIN. After finding the NH of the network, starting with the nearest node as cluster head, the node selection is finalized. Then selected nodes are utilized to form the DCT.DCT is a hierarchical tree structure, which covers the entire WSNs. DCN collects the data from the cluster heads and delivers it to sink or BS. Selecting DCN with better connection time and best communication range reduces energy consumption due to long range node to node data transfer. While the sensor nodes are on high mobility, the selected DCN keeps the communication with the cluster head for a longer time and there is no need to update the tree structure. In order to keep the lifetime of whole network in harmony DCN is also newly selected every time when the new cluster heads are elected. New DCN selection also is carried out by sink, which is based on the mobility of the new cluster head.


## 4.2. Intracluster Communication

Considering ambiguous large-scale WSNs, sensor nodes have been densely deployed over the region. During the setup phase, the beacon signal is used to identify the sensor nodes location and position. Once the nearby nodes are identified, random algorithm or election algorithm is used to elect the cluster head. After the cluster head selection, the next phase DCT formation is initiated.In the proposed method, the threshold valueUabn has been calculated in (1) by adding the flag value with the multiplication of factors such as the total number of neighbor nodes, residual energy, and current speed of the sensor node, where FC is the flag (set FC=1 for previous round cluster head and FC=0 for sensor node having a chance to act as current round cluster head based on Uabn), En-current is the current sensor node energy, Vn-current is the current speed of the sensor node, Emax⁡ is the initial energy, and Vmax⁡ is the maximum speed of the sensor node. In order to avoid the election of high mobility node as cluster head, ((Vmax⁡-Vn-current)/(Vmax⁡+Vn-current)) instead of (Vmax⁡/Vn-current) may be considered. The expected number of sensor nodes in each cluster is m=NS/CH. Those nodes having maximum residual energy, maximum number of cluster members, and maximum connection time can be elected as cluster head in (1):
(1)Uabn=(Vmax⁡-Vn-currentVmax⁡+Vn-currentFC+(Nb-currentNmax⁡-Nb-current×Emax⁡-En-currentEmax⁡×Vmax⁡-Vn-currentVmax⁡+Vn-current)).
It is visualized that the 2D network position of the cluster headband sensor node a at time t is characterized in (2) as follows:
(2)Xb=xb+vb*cos⁡⁡θbt;Yb=yb+vb*sin⁡θbtXa=xa+va*cos⁡⁡θat;Ya=ya+va*sin⁡θat,
where (x,y) is the primary node location, v is the speed, θ is the moving path angle between (x,y), and t is the connection time. Then, the subscript (a,b) corresponds to sensor node a and cluster head b, respectively. Let the Rabt be denoted as (3)
(3)Rabt≥((Xb-Xa)2+(Yb-Ya)2)1/2.
At time t=0, each sensor node receives an advertisement message from any one of the cluster heads. Hence, the above 2D network equation (3) is considered and simplified into (4)
(4)Rabt≥((xb-xa)2+(yb-ya)2)1/2ift=0.
Now, ΔRabt,t+s is the difference between Rabt and Rabt+s at time instance t and t+s. Let ΔRabt,t+s be found using (4):
(5)ΔRabt,t+s=Rabt-Rabt+sif(n,s)∈t,s=0,1,2.…n.
However, for ΔRabt,t+s=0, there is no sensor nodes on mobility within a cluster. ΔRabt,t+s is the negative value for sensor nodes in a cluster moving away from the cluster head; ΔRabt,t+s is the positive value cluster head and cluster member moving towards to each other. Now, the RSS (received signal strength) can be calculated at any time instance t and t+n in (6)
(6)RSSabt=RSSab-currentt-RSSab-minRSSabt+s=RSSab-currentt+s-RSSab-min∀s∈t,
whereas RSSab-min is the minimum required threshold value and RSSab-currentt+s is the current threshold value at time instance t. If RSS is a positive value, the cluster members join in an appropriate cluster and communicate with corresponding cluster head. In this case, ΔRSSabt,t+s is the difference between RSSabt and RSSabt+s, which can be found from (6)
(7)ΔRSSabt,t+s=RSSabt-RSSabt+s,
wherever, ΔRSSabt,t+s≤0, cluster member move away from the current position of the cluster head. ΔRSSabt,t+s≥0, both cluster member and cluster head move towards each other from their current position. Gabn is the value assigned to sensor nodea on round, which indicates its robustness for connection with cluster headb. The dimensionless value δG,ζG,ηG, and κCT is a linear combination with constant coefficients between0 and1. The coefficients represent the consequence of each factor and are denoted in (8) as follows:
(8)δG+ζG+ηG+κCT=1.
Therefore, (8) can be originated into Gabn and in (9) represented as
(9)Gabn=(δT×(Emax⁡-Eb-currentEb-current×Nb-current))+(ζT×(1-RSSab-minRSSab-current))+(ηT×(dba-RabtRabt))+(κCT×(Δtabbtcf)),
where Emax⁡ is the initial energy, Eb-current is the cluster head current energy, Nb-current is the number of current cluster members for cluster head b, RSSab-min is the minimum required RSS from a and b, RSSab-current is the current RSS betweena and b, Rabt is the distance betweena andb at any time instance t, dba is the maximum coverage distance betweenb anda, Δtabb is the estimated connection time fora begins its transmission tob, and tcf is the current duration of the data frame forb.


## 4.3. DCT Communication

After the intracluster communication phase, DCT formation phase is initiated. It is based on the threshold value, connection time, and network traffic. DCT makes a communication link between the cluster head and sink. Let it be visualized that the 2D network position of the cluster headb and DCNe orh at timet is
(10)Xb=xb+vb*cos⁡θbt;Yb=yb+vb*sin⁡θbtXe=xe+ve*cos⁡⁡θet;Ye=ye+ve*sin⁡θetXh=xh+vh*cos⁡⁡θht;Yh=yh+vh*sin⁡θht.
On each round, the distance between cluster headb to DCNe andh has been calculated from (10). Let the distance Rbet and Reht be denoted in (11)
(11)Rbet≥((Xb-Xe)2+(Yb-Ye)2)1/2.Reht≥((Xe-Xh)2+(Ye-Yh)2)1/2,0≤t≤n
Let t=0; the distance Rbet and Reht in (11) can be considered as
(12)Rbet≥((xb-xe)2+(yb-ye)2)1/2Reht≥((xe-xh)2+(ye-yh)2)1/2,t=0,∀n∈t.
For any cluster head to DCN or DCN to DCN or sink to DCN communication, the threshold value Uuvp has been calculated in (13) by adding total number of DCN with multiplied factors such as the residual energy, and current speed between cluster head to DCN or DCN to DCN. Let u be considered instead of b (it represents that cluster head or sink or DCN), v as a substitute of e and h (it signifies that DCN):
(13)Uuvp=Hv+(Ev-max-Ev-currentEv-max×Vv-max-Vv-currentVv-max+Vv-current),
where Hv is the count for DCN, Ev-current is the current cluster head energy, Vv-current is the current speed of the cluster head, Ev-max is the initial energy, and Vv-max is the maximum speed of cluster head. Let ΔRuvt,t+n be the diversity with Ruvt and Ruvt+n. At the time instance t and t+n, ΔRuvt,t+n is represented in (14)
(14)ΔRuvt,t+n=Ruvt-Ruvt+n,t=0,1,2…n,∀n∈t.
However, ΔRuvt,t+n=0, both nodes (cluster head and DCN or any two DCN) not in mobility, which is separated in even distance. ΔRuvt,t+n is the negative value for both nodes moving away; ΔRuvt,t+n is the positive value for both nodes moving towards each other. Consequently, the RSS (received signal strength) between any two nodes, at the time instance t and t+n is calculated in (15)
(15)RSSuvt=RSSuv-currentt-RSSuv-minRSSuvt+n=RSSuv-currentt+n-RSSuv-min∀n∈t,
where RSSuv-min is the minimum required threshold value and RSSuv-currentt+n is the current threshold value. If RSSuvt+n is a positive value, then the cluster head or DCN has a likelihood to join with nearest DCN, which can establish the communication with corresponding nodes. ΔRSSuvt,t+n can be found using (15) as follows:
(16)ΔRSSuvt,t+n=RSSuvt-RSSuvt+n,∀n∈t
wherever ΔRSSuvt,t+n≤0, both nodes moving away from their current position. ΔRSSuvt,t+n≥0, both nodes moving towards each other. The dimensionless value δCT,ζCT,ηCT, and κCT is a linear combination with constant coefficients between0 and1. The coefficients represent the consequence of each factor and are denoted as (17)
(17)δCT+ζCT+ηCT+κCT=1.Guvp is the value assigned to all u on each round, which indicates its heftiness for connection with v:
(18)Guvp=(δCT×(Ev-max-Ev-currentEv-current×Nv-current))+(ζCT×(1-RSSuv-minRSSuv-current))+(ηCT×(duv-RuvtRuvt))+(κCT×(ΔtuvvtCTf(Ψ))),
where Ev-max is the initial energy ofv, Ev-current is the current energy of v, Nv-current is the total number of cluster head or DCN connected with v, RSSuv-min is the minimum required RSS to make a connection from u and v, RSSuv-current is the current RSS to establish a connection betweenu and v,duv is the maximum coverage distance between u and v,Ruvt is the distance between u and v at any time instance t, Δtuvv is the estimated connection time for u begins its transmission to v, and tCTf(Ψ) is the current duration of the data frame for v.


## 4.4. Frame Duration

Let us consider the number of current cluster MembersMc and the number of expected cluster members Me can be derived from the following equation (19):
(19)Mc=Me-(Md+Ms)Me=Nc-CH-CTCH;Nc=Nt-Nd,
where Mc is the current cluster member from one cluster, Me is the expected number of cluster member, Md is the number of cluster member dead, Ms is the total number of cluster members on sleep state, Nc is the total number of current sensor nodes, Nt is the total number of sensor nodes over a network, Nd is the number of sensor nodes dead, and CH is the cluster head. Now, the current duration of the data frame tcf from each cluster is denoted in (20)
(20)tcf=LpRb×Mcortcf=LpRb×Me,
where Lp is the data packet length and Rb is the transmission bit rate.


## 4.5. Steady State Phase

On steady state phase, each cluster member and the corresponding cluster head build intracluster communication with each other. Initially, all the cluster members send the sensed data to cluster head in an allocated TDMA time slot. Thereafter, the cluster head aggregates the received data, and then forward the data packet to the DCN. Again, DCN aggregates the data packet from its cluster head and then forward to the sink with DCT. In DCT communication, direct sequence spread spectrum techniques can be used to transfer the data packets from the cluster head to DCN and sink. DCT discovers an optimal path between the cluster head and the sink based on the distance, connection time, threshold value, and residual energy. Based on the optimal path, the entire cluster head forwards the data packets to the nearest DCN. Now, the DCT becomes responsible for forwarding an entire data from the cluster head to sink.


## 5. Results and Discussion

In this section, the simulation results are used to evaluate the performance of the proposed protocol under various parameter settings. The network simulator was used to carry out a performance study of CIDT to compare with LEACH and MBC. Considering 500 nodes of WSNs, all the nodes were randomly deployed in a square region of 1000 × 1000 m2, the size of data packet is 512 bytes, the transmission range within the cluster 40 m, the transmission range between the cluster 80 to 120 m, the sensing range is 20 m, and the base station is located in (x=500, y=1050). Further communication energy parameters can be set as Eelec = 50 nJ/bit/m2 and Eamp = 0.0013 pJ/bit/m4. Then, the energy required for data aggregation is set into EDA = 50 nJ/bit/signal.Based on CIDT, the network performance was simulated in terms of the packet delivery ratio (PDR), throughput, delay, total energy, and speed. Figures6, 7, 8, and 9 illustrate the relationship between the number of deployed nodes and the performance of the network (PDR, throughput, total energy consumption, and delay). It is worth noting that LEACH, HEED, and MBC fail to prolong the PDR, throughput, total energy consumption, and delay as the number of node increases. However, CIDT makes better performance linearly even the number of sensor node increases over the network. In large-scale mobility-based WSNs, unreliable links may cause the packet loss and retransmissions. In that case, it may increase the energy consumption of sensor nodes. In addition, it may reduce the PDR and throughput. Although, CIDT can provide stable links and guarantee the balanced energy conservation over the network. Therefore, it can be conclude that CIDT protocol has been mended adapting to the high mobility environment.Figure 6
Packet delivery ratio versus number of nodes.Figure 7
Throughput versus number of nodes.Figure 8
Total energy versus number of nodes.Figure 9
Delay versus number of nodes.Figures10 and 11 show that CIDT has superior performance when compared to MBC, HEED, and LEACH in mobile sensor ambience. In the simulation results, it can be enunciated that CIDT protocol has provided stable links and mended adapting to the high mobility environment. On high mobility environment, CIDT makes better PDR and less end-to-end delay.Figure 10
Packet delivery ratio versus speed.Figure 11
Delay versus speed.Finally, it can be concluded that the proposed CIDT protocol can save the sensor nodes residual energy, extend the network lifetime and network reliability. It is mended adapting to the high mobility environment with better communication quality.


## 6. Conclusions

With the growing impact of WSNs on real time civil and military applications, numerous sensor nodes are required to monitor the large-scale areas. Cluster tree is a proficient method to construct suspicious network management architecture. The ultimate goal is to exploit the network lifetime, residual energy, throughput, PDR, and stable link for mobile sensor nodes. In this paper, CIDT (cluster independent data collection tree) proposed for mobility-based WSNs, each cluster member chooses the cluster head with better connection time, and RSS. Then, forward the data packets to the corresponding cluster head in an allocated time slot. Consequently, the sink or DCN select the one-hop neighbor DCN or cluster head with the maximum of threshold value, RSS, connection time, and less network traffic. From the simulation results, it is evident that CIDT provides more stable links, throughput, PDR with a reduction of network traffic and a condensed sum of energy utilization than LEACH, HEED, and MBC.



---

*Source: 518268-2014-04-16.xml*