# Sensors Grouping Hierarchy Structure for Wireless Sensor Network

Authors: Ammar Hawbani; Xingfu Wang; Saleem Karmoshi; Lin Wang; Naji Husaini
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

There are many challenges in implementation of wireless sensor network systems: clustering and grouping are two of them. The grouping of sensors is computational process intended to partition the sensors of network into groups. Each group contains a number of sensors and a sensor can be an element of multiple groups. In this paper, we provided a Sensors Grouping Hierarchy Structure (GHS) to split the nodes in wireless sensor network into groups to assist the collaborative, dynamic, distributed computing and communication of the system. Our idea is to partition the nodes according to their geographical maximum covered regions such that each group contains a number of nodes and a number of leaders. To evaluate the performance of our proposed grouping structure, we have implemented a Grouped based routing and Grouped based object tracking. The proposed grouping structure shows a good performance in energy consumption and energy dissipation during data routing and it generates a little redundant data during object tracking.


---

## Body

## 1. Introduction

Like other distributed systems, WSNs are subject to a variety of unique constraints and challenges such as restricted sensing and communication ranges as well as limited battery capacity [1, 2]. These challenges affect the design of WSN [3] and bring some issues such as coverage, connectivity, network lifetime, self-managing, data aggregation, energy dissipation and energy balancing, clustering, and grouping [4, 5]. In WSNs, the node contains three main subsystems: the sensing subsystem contains one or more physical sensor devices and one or more analog-to-digital converters as well as the multiplexing mechanism to share them. The processor subsystem executes instructions pertaining to sensing, communication and self-organization [2]. The communication subsystem contains the transmitter and receiver for sending or receiving information. Due to limited range of communication, establishing the direct connection between a sensor and the base station may make the nodes transmit their messages with such a high power that their resources could be quickly depleted. Thus, the collaboration of nodes ensures the communications between distant nodes and base station. In this way, the intermediate nodes transmit messages so that a path with multiple links or hops to the base station is established [2, 6, 7]. However, the collaborative working of nodes is more critical and more complicated because of WSN natural and challenges like energy dissipation, energy balancing, location tracing, and latency. The sensors work collaboratively in many applications in our daily lives, including data collection, military applications, monitoring, and space applications [8]. For obtaining a stable collaborative work among sensors, the nodes must be able to organize themselves in structures (i.e., hierarchical structure) such that the objectives of network are achieved using the minimum cost of communication. Generally, the clustering is the most common used structure for WSNs. The clustering techniques for WSNs can be classified based on the overall network architectural and operation model and the objective of the node grouping process including the desired count and properties of the generated clusters. The research community has pursued it widely in order to achieve the network scalability objective [9]. Many of clustering algorithms [10–12] focused mainly on how to yield stable clusters with node reachability and route in environments using mobile nodes without much concern about critical design goals of WSNs such as network connectivity and coverage [9]. During the recent years, there are also many clustering algorithms designed especially for WSN, most of them mainly focused on energy dissipation, energy-balancing, and so forth.In the literature, many protocols to reduce energy consumption have been proposed. The Low Energy Adaptive Clustering Hierarchy (LEACH) protocol [13, 14] is a cluster-based routing protocol for WSN networks that perform load balancing and ensure scalability and robustness by routing via cluster-heads and implement data fusion to reduce the amount of information overhead [15]. LEACH utilizes a randomized rotation of local cluster head to evenly distribute the energy load among the sensors in the network. After LEACH, the Power-Efficient Gathering in Sensor Information System PEGASIS [16] comes with new improvements: in PEGASIS each node communicates only with a nearby neighbor in order to exchange data, but LEACH uses single-hop routing in which each sensor node transmits information directly to the cluster-head or the sink. Regarding clustering in WSN, [17] surveys different energy efficient clustering protocols for heterogeneous wireless sensor networks and compares these protocols on various points like location awareness, clustering method, heterogeneity level, and clustering attributes. Moreover [18] presented efficient request-oriented coordinator methods for hierarchical sensor networks.On the other hand, the traditional structures in WSNs can be categorized into data centric and location based. References [19, 20] provided two routing protocols based on data centric. In [19], Sensor Protocols for Information via Negotiation (SPIN) uses the data negotiation scheme among sensor nodes to decrease data redundancy and save energy. Direct Diffusion [20] is another data-centric routing protocol. The data generated by sensor nodes is named attribute-value pairs. When a sink node queries a certain type of information, it will send a request and the sensed data can be aggregated and then be transmitted back to the sink node. Location-based routing protocols can get the information of nodes location via GPS or any estimation algorithms based on received signal strength. Once the location information is known, the consumption of energy could be largely minimized using power control techniques [21, 22]. Based on theoretical analysis and numerical illustration under different energy and traffic models the [23] Distance-based Energy Aware Routing (DEAR) proposed an efficiently reducing and balancing of energy consumption in WSNs. During the routing process, DEAR treats a distance distribution as the first parameter and the residual energy as the secondary parameter. In the aims at maximizing the network lifetime and minimizing the energy consumption, the Two-Level Cluster base Protocol (TLCP) [24] organizes sensor nodes into clusters and forms a cluster among the cluster heads. In TLCP each cluster head transmits its data to the header of this cluster instead of transmitting directly to the far away base station and only the header can transmit data directly to the base station. The authors in [25] describe a routing protocol for wireless sensor networks based on the inclusion of routing information in the packets when minimum cost forwarding method is used. The routing table on BS is formed in the network setup phase and updated after any change in network topology reported by sensor nodes. CCM (Chain-Cluster based Mixed routing) is explained in [26]; this algorithm makes a full use of the advantages of LEACH [13] and PEGASIS [16] and provided an improved performance. CCM algorithm divides the WSN into a few chains and runs in two stages. In the first stage, sensor nodes in each chain transmit data to their own chain head node in parallel, using an improved chain routing protocol. In the second stage, all chain head nodes group as a cluster in a self-organized manner, where they transmit fused data to a voted cluster head using the cluster based routing.As shown in Figure1, we assumed that the interested field is covered with the minimum number of nodes such that the overlapped regions between the nodes are minimized and the nodes are expanded to cover the interested field completely. As well as, we assumed that the nodes have the same communication range indicated by the dotted circle. With such assumptions, unfortunately, if the CH nodes have the same communication range, the static clustering or dynamic clustering will not perform as efficient as peer-to-peer network.Figure 1
Two different networks. The filled small circle indicates the location of node, and the dotted circle indicates the communication range of node.
(a)
Random 100 nodes
(b)
137 nodes deployed using Zigzag sachemThis paper intended to develop and design a grouping algorithm to be used for partitioning the nodes into groups according to themaximum overlapped regions in the field. We will see the impact of this model in(i)
data routing and energy saving (Section4),(ii)
object tracking and energy balancing (Section5),(iii)
avoiding data redundancy (Section6).The difference between clustering and grouping is simply as below:(i)
Clustering is performed by assigning each node to a specific cluster; that is to say, each node belongs to only one cluster [8]. There is only one CH in each cluster.(ii)
Grouping model is to divide the network into groups such that each node can belong to more than a group in the same time. There is more than one leader for the same group.The rest of this paper is organized as follows. In Section2, the grouping model and grouping algorithm are explained. The suggested network model is described in Section 3. In Section 4, we have proposed a very simple strategy for data routing based GHS. In Section 5, based on GHS, an object tracking strategy is proposed. A mechanism for avoiding data redundancy is explained in Section 6. The simulation results are shown in Section 7. Section 8 concludes this work.


## 2. Grouping Structure

Our main idea is to partition network’s nodes into groups according to theirgeographical maximum covered regions in such way that each group contains a number of nodes and a number of leaders; that is, the network in Figure 2(a) contains 8maximum covered regions (indicated by small filled circles and given a number from small filled circle 1 to small filled circle 8). That is to say, this network can be partitioned into eight groups. In Figure 2(b) the graph vertices are shown (small filled circle 1 to small filled circle 8) and each vertex represents a group of sensors; that is, the group (small filled circle 1) contains four sensors, namely, 1, 2, 3, and 4. Two groups are said to be adjacent if they contain one or more sensors in common; that is, groups ((small filled circle 1) and (small filled circle 2)) are adjacent since they have two sensors in common, namely, 3 and 4. The common sensors are called the leader of adjacent groups and they represent the edge of network graph.Figure 2
12 nodes deployed randomly.
(a)
Sensors deployed in an interest area. The small filled circles are the maximum overlapped regions (the maximum covered regions). The big white unfilled circle indicates the communication range of the node
(b)
Grouping graph, underlined sensors are the leaders of groupsIn the following, we will address the grouping problem using a simple mathematical model. Here we can present the network as a list of vectors collected by all sensors in the field. The network ofn sensors is represented by a square matrix (n×n). Consider(1)A∗=11⋮0011⋮10⋯00⋮11n×n,aij=1,siandsjare  overlapped,1,i=j,0,siandsjarenotoverlapped.For example, the network in Figure 2 is represented by a square matrix (12 × 12):(2)A∗=111100000000111100000000111100001000111100011000000010100110000001010000000010100000000101011000001100011100000010001111000010000111000000000111.We can find themaximum covered regions by partitioning A∗ into square submatrices A1,A2,A3,… such that all elements of submatrix aij=1, as well as the subsquare matrix, contain themaximum number of rows and columns. Each square submatrix represents a group of sensors. For example, the network in Figure 2 is partitioned into eight square sub matrices listed as below: (3)A1=1111111111111111g1=1,2,3,4,A2=111111111g2=3,4,9,A3=111111111g3=4,8,9,A4=1111g4=6,8,A5=1111g5=9,10,A6=111111111g6=10,11,12,A7=111111111g7=5,10,11,A8=1111g8=5,7.If WSN is connected then A∗n×n can be partitioned into square submatrices A1,A2,A3,…,Ai, where i is an integer and 1≤i≤n-1.We divide the nodes into a set ofgroups dynamically such that G∗=Gi,Gj,Gk,…, where i,j and k are integers indicating the number of sensors in thegroupsGi, Gj, and Gk, respectively. Note that the term ofgroups is different from the termclusters.A groupGk∈G∗ contains 1+kk-1subareas and among them there will be one area which is k-covered, k areas which are 1-covered, k areas which are 2-covered…, and k areas which are k-1 covered. Note that when an object moves in x-covered area (x>1,x∈Z) it will be detected by x sensors. Hence, more traffic will be generated which leads to more redundant data and more energy consumption in the network. In the range of any sensor s∈Gk there are 1+k(k-1)/2 subareas, among themone area is  k-covered, 1  area is  1-covered, 2 areas are  2-covered, 3 areas are  3-covered…, and  k-1 areas are  k-1  covered; that is, see Figure 3.Figure 3
A groupG4.
(a)
The coverage degree of groupG4
(b)
The 13 subareas of groupG4A groupGk∈G∗ contains RGk=1+kk-1 regions (i.e., Figure 3(b)). We can count the RGk easily by considering the number of regions in Gk with no repetition; that is to say,(4)RGk=∑j=0kRsj,where Rsj is the number of regions within the range of sj, and it is easy to see that the number of areas inside the range of node sj is satisfying the recursive relation:(5)Rsj∈Gk=fk=k+fk-1-1,k≥1,f1=1.We can solve this equation using generation functions and obtain(6)Rsj∈Gk=1+kk-12,Rsj∈Gk=1+k2.By removing the repetition from (4), we can get(7)RGk=1+k2+k-1+k-2+⋯k-k-1,RGk=1+k2+∑i=1k-1k-i=1+k!2!k-2!+kk-12=1+kk-12+kk-12=1+kk-1.Among RGk there will beone area which is k-covered, k areas which are 1-covered, k areas which are 2-covered…, and k areas which are k-1covered. Let Cx,k (x≤k) be the notation for x-covered region in RGk and let ΦCx,k be the number of Cx,k in RGk; hence ΦC0,k=0, ΦCk,k=1, and, generally, ΦCx,k=k, where k-1≥x≥1 and then it is easy to see that(8)RGk=ΦC0,k+ΦC1,k+ΦC2,k+⋯ΦCk,k=∑i=0kΦCi,k=0+k+k+⋯+1=1+kk-1.Furthermore, among the Rsj∈Gk there will beone area which is k-covered, 1 area which is 1-covered, 2 areas which are 2-covered, 3 areas which are 3-covered…, and k-1 areas which are k-1covered; that is, see Figure 3(a). We denoted to the x-covered regions in the range of node sj by cx,j (x≥0), and let θcx,j be the number of cx,j regions; then, for any sj∈Gk, the θci,j=i, where  k-1≥i≥0. We can obtain that θc0,j=0 and θck,j=1. It is obvious that(9)Rsj∈Gk=θc0,j+θc1,j+θc2,j+⋯θck,j=θck,j+∑i=0k-1θci,j=θck,j+0+1+2+3+⋯+k-1=1+kk-12.Therefore, we can obtain the number of regions Rsj∈G∗sj, where G∗sj is the set ofassociated groups of sj such that G∗sj=Gx∣Gx∈G∗andsj∈Gx. Let Υ=G∗sj; then(10)Rsj∈G∗sj≤∑Gx∈G∗sjRsj∈Gx-Υ-1.Any object oi∈M moves in a group Gk∈G∗, its location should be detected within the group range with respect to the Probability space Ω(Gk∈G∗)=C1,k,C2,k,…,Ck,k. However, any object oi∈M moves in the range of node sj∈G∗sj; its location should be detected with respect to the Probability space Ωsj∈G∗sj=c1,j,c2,j,…,ck,j.This grouping model has advantages since it makes the WSNs stress-free in many aspects such as data routing and data redundant avoiding. Below, we will provide adistributed grouping algorithm (Algorithm 1), which is executed inside the processing unit of the sensor node. However, it utilizes the information of nearby sensors to find themaximum covered regions. The symbols used for grouping algorithms are listed in Table 1.Table 1
The symbols used for grouping algorithm.
Symbol
Meaning
S
A set of sensors.
D
Euclidean distance.
V
i
The list of neighbor nodes ofsi. Here we call V the vector of sensor.
V
i Is the number of sensor inside Vi.
D
=
(
x
s
i
-
x
s
j
)
2
+
(
y
s
i
-
y
s
j
)
2
∀
s
j
∈
S  do:
if (ri + rj < D) do:
Vi_add(sj);
N
i
The list of neighbor vectors forsi.
∀
s
j
∈
V
i  do:
find  Vj  and then add  Vj  to  Ni  by calling:
Ni_add(Vj).
That is to find the vector for each sensorsj such that sj∈Vi  i≠j.
The number of vectors inNi is denoted by Ni.
F
i
The list of filtered neighbor vectors forsi. The filtering process is running as:
∀
V
a
∈
N
i  do:
Vx←null;
∀sc∈Va  do:
if (sc∈Vi) do:
Vx.add(sc);
Fi_add(Vx)
That is to say, the sensor in theNi will be add to Fi if and only if they are belong to Vi, otherwise they will be ignored. Fi is the number of vectors inside Fi.
G
∗
(
s
j
)
The associated groups ofsi, such that G∗(sj)={Gx∣Gx∈G∗andsj∈Gx}.
F
i
[
n
]
Get the filtered vector with indexn.Algorithm 1:Grouping algorithm.
FindG∗(si)
Input:si,S
Output:G∗(si)  the associated groups of si
(1)Vi←si.Vector
(2)for (int  k←0; k<Fi; k++)
(3)
(4)Vk←Fi[k];
(5)sk←Vi[k];
(6)if (Vk=2)
(7)
(8)   Gk←Vk
(9)   G∗(si) += Gk
(10)
(11)else
(12)
(13)for (int m←k+1; m<Fi; m++)
(14)
(15)  Vm←Fim;
(16)  if (sk∈Vm)
(17)
(18)    GVk∩Vm←Vk∩Vm
(19)    G∗(si) += GVk∩Vm
(20)
(21)
(22)
(23)Algorithm1 shows how the sensor node si aware its associated groups G∗sj=Gx∣Gx∈G∗andsj∈Gx.By analyzing Algorithm1, we can predict the resources (i.e., memory, communication bandwidth, and energy) it requires. Assume that n=Fi is the input size (the number of filtered vectors); then it is easy to compute the time complexity of Algorithm 1:(11)Tn=n-1+n-2+n-3+⋯+3+2+1,Tn=∑j=1nn-j,Tn=12nn-1.The worst-case running time is(12)Tn=θn2.


## 3. Network Model

We model theGrouped based network using aweighted graphG, where graph vertices correspond togroups and graph edges correspond toleader sensors. By “leader sensors,” we mean the sensors that belong to more than one group. Two groups are to be adjacent if they have one sensor or more in common.We consider astatics GraphG=V,E,μ to represent the topology of sensors deployed in a sensing field, where V indicates the vertices, E indicates the edges, and μ indicates the weight function where μ:E→R+ supplies the distance between adjacent vertices in E. Here each vertex in V is represented by a group of sensors. Note that V is different from previous approaches where each sensor node represents a vertex.We assume that each sensor has a unique identifier (ID) and all sensors are aware of their geographical location andμv,v=0 for any node v∈V. We assume that G is connected; that is, there is a path of nodes connecting any pair of nodes in the network.The nodes organize themselves into groups according to Algorithm1 such that G∗=Gi,Gj,Gk,…. A group Gx∈G∗ contains a number ofsensors,that is, Gx=s1,s2,…,sv, Gx=v, and multiple number ofleaders. The set of groups G∗sj is called the associated groups of sj, such that G∗sj=Gx∣Gx∈G∗andsj∈Gx. The leaders of groups are not randomly chosen (Table 2). However, the node can be a leader if and only if it belongs to more than one group; that is, in Figure 2, sensor 7 cannot be a leader since it belongs to only one group.Table 2
The groups and leaders of network (Figure2).
Node
Groups
Members
Leaders
1
1
(1, 2, 3, 4)
4, 3
2
1
(1, 2, 3, 4)
3, 4
3
1, 2
(1, 2, 3, 4), (3, 4, 9)
3, 4, 9
4
1, 2, 3
(1, 2, 3, 4), (3, 4, 9), (4, 8, 9)
3, 4, 8, 9
5
8, 7
(5, 7), (5, 10, 11)
10, 11, 5
6
4
(6, 8)
8
7
8
(5, 7)
5
8
3, 4
(4, 8, 9), (6, 8)
4, 8, 9
9
2, 3, 5
(3, 4, 9), (4, 8, 9), (9, 10)
3, 4, 8, 9, 10
10
5, 6, 7
(9, 10), (10, 11, 12), (5, 10, 11)
5, 9, 10, 11
11
6, 7
(10, 11, 12), (5, 10, 11)
5, 10, 11
12
6
(10, 11, 12)
10, 11


## 4. Data Routing

In this section we explain a simple data routing based on grouping model. When a source node has data to send, it first started by finding the minimum distance group to the base station (Algorithm2) and then from the selected group chooses the next hop to forward the data. The next hop can be selected according to either minimum distance to the next target node or maximum energy of target node. After maintaining the next hop (target node), the leader of the selected group will transmit the data directly to target node. After the operation of receiving data is finished, the target node finds its minimum distance group and next transmits the data recursively until the data reach the sink node. The flow chart of routing process is illustrated in Figure 4.Algorithm 2:Data routing algorithm.
Input: si is the Source Node
Output: send data to BS directly, or forward data via multi-hop path.
(1)DataRouting(si, Message msg)
(2)
(3)  TargetGroup←  GetMinDistanceGroupFor(si);
(4)st← MinDistanceSensor(TargetGroup); //st is the target node
(5)if (st.ID ≠ SinkNode.ID)
(6)
(7) si.SendData(st);
(8)   st.ReceiveData(si);
(9)   DataRouting(st, msg);
(10)
(11)else
(12)
(13)si.SendData(SinkNode);
(14)     SinkNode.ReceiveData(si);
(15)
(16)Figure 4
Grouped based data routing.
(a)
Flow chart of data routing
(b)
Logic structure of the groups in Figure2


### 4.1. Energy Saving during Data Routing

The grouping model provided an efficient energy management during communication. Consider groupG4=s1,s2,s3,s4 of network depicted in Figure 2, and assume that s1 has a data packet to send. Some of routing protocols just select a neighbor node to be the next hop and then transmit the data packet from s1 to the selected neighbor node. In many cases, this selection could lead to wastage of energy consumption; for example, if the selected neighbor node is s2 then the consumed energy to transmit the packet from s1 to s2 is wasted. Our grouping model avoided such situations as below.(1)
In the same group, thenone-leader tonone-leader routingalways leads to wastage of energy consumption. Note that the nodes in each group can communicate directly by one hop and the leaders of group acts as a gateway for the group.(2)
In the same group, theleader toleader routingsometime leads to wastage of energy consumption.(3)
In the same group, theleader tonone-leader routingalways leads to wastage of energy consumption.The logical structure of grouping model for network deployed in Figure2 is explained in Figure 4(b). When anone-leader node has data to send, it just selects one of theleaders in the group and then transmits data to the selectedleader. Theleader can be selected upon three main parameters:(1)
the residual energy ofleader (i.e., theleader with more energy win),(2)
the distance to source node (i.e., the nearestleader win),(3)
the current state ofleader (i.e., busy or free).


## 4.1. Energy Saving during Data Routing

The grouping model provided an efficient energy management during communication. Consider groupG4=s1,s2,s3,s4 of network depicted in Figure 2, and assume that s1 has a data packet to send. Some of routing protocols just select a neighbor node to be the next hop and then transmit the data packet from s1 to the selected neighbor node. In many cases, this selection could lead to wastage of energy consumption; for example, if the selected neighbor node is s2 then the consumed energy to transmit the packet from s1 to s2 is wasted. Our grouping model avoided such situations as below.(1)
In the same group, thenone-leader tonone-leader routingalways leads to wastage of energy consumption. Note that the nodes in each group can communicate directly by one hop and the leaders of group acts as a gateway for the group.(2)
In the same group, theleader toleader routingsometime leads to wastage of energy consumption.(3)
In the same group, theleader tonone-leader routingalways leads to wastage of energy consumption.The logical structure of grouping model for network deployed in Figure2 is explained in Figure 4(b). When anone-leader node has data to send, it just selects one of theleaders in the group and then transmits data to the selectedleader. Theleader can be selected upon three main parameters:(1)
the residual energy ofleader (i.e., theleader with more energy win),(2)
the distance to source node (i.e., the nearestleader win),(3)
the current state ofleader (i.e., busy or free).


## 5. Object Tracking and Energy Balancing

Consider a set ofm mobile objects M=o1,o2,o3,…,om moving randomly in the range of set of n none-mobile nodes S=s1,s2,s3,…,sn. The nodes of network are partitioned into groups dynamically such that G∗=Gi,Gj,Gk,…. We assume that any node sj∈S is aware of theassociated groups to which it belongs, such that G∗sj=Gx∣Gx∈G∗andsj∈Gx. Regarding energy balancing, when there is a notification message (i.e., Insert, Rescue, and Delete) to be sent from sj to its associated groups G∗sj, and sj will not be sent to all nodes in G∗sj separately. However, sj build aNotification TreeNTsj to manage the notifications (Algorithm 3), which will be sent to all nodes in G∗sj with respect to energy saving of sj and energy balancing of G∗sj. TheNotification Tree ensures that all nodes in G∗sj will consume approximately the same amount of energy during sending notifications.Algorithm 3:Build the Notification Tree.
Input: sj
Output: NT(sj)
(1)Root←sj;
(2)Gj←(Vj,Ej)//Vj={sx∣sx∈G∗(sj)}  and  Ej⊆[Vj]2
(3)Gj,i←Gj-sj//{Gj,0,Gj,1,…,Gj,i}  subgraphs
(4)for (int  i←0; i<Gj,i; i++)
(5)
(6)Tj,i←BuidSpanningTree(Gj,i)//build the spanning tree for each subgraph.
(7)Root.childern.add(Tj,i)
(8)


### 5.1. Building the Notification Tree

The main objective ofNotification Tree is to distribute the energy dissipation among the nodes of G∗sj as evenly as possible such that each node in G∗sj gets notified and consumes the same amount of energy. Each node sj in the network has aNotification TreeNTsjand its root issj.For nodesj, consider graph Gj=Vj,Ej, where Vj=sx∣sx∈G∗sj and Ej⊆Vj2 as shown in Figure 5. The operation sx∈G∗sj is true if sx∈Gi and Gi∈G∗sj. Consider sj asarticulation vertex or a cut vertex of Gj such that Gj-sj=Gj,0,Gj,1,…,Gj,i, where Gj,i is a component or subgraph of Gj.Figure 5
Notification tree.
(a)
Random 5 nodes
(b)
GroupsG∗s1
(c)
Undirect graphG1
(d)
Components ofG1-s1
(e)
N
T
s
1
(f)
N
T
s
2, NTs3, NTs4, NTs5, and NTs4When there is a notification message to be sent fromsj to its associated groups G∗sj, sj will send Gj-sj messages. That is to say, it will send a message to each component of Gj-sj. Each Gj,i∈Gj-sj will build a spanning tree Tj,i which will be attached to the root node of NTsj (Algorithm 4).Algorithm 4:Build spanning tree Tj,i for the subgraph Gj,i∈Gj-sj.
Input: Gj,i
Output: Tj,i
(1)minDegreeVertex←SelectMinDegreeVertext(Gj,i);
(2)Tj,i←null;
(3)Tj,i.Sensor←subRootSensor(minDegreeVertex,Gj,i);
(4)if (Tj,i.ID≠-1)//the link list is Empty
(5)LinkNoneLeaderSensors(Tj,i,minDegreeVertex,Gj,i);
(6)LeaderSensor←selectLeaderSensor(minDegreeVertex,LinkList);
(7)if (LeaderSensor≠null)
(8)LinkLeaderSensor(Tj,i,LeaderSensor);
(9)minDegreeVertex.wasVisited←true;
(10)incidentVertex←getIncidenVertext(LeaderSensor,Gj,i);
(11)while (incidentVertex≠null)
(12)
(13)LinkNoneLeaderSensors(Tj,i,incidentVertex,Gj,i);
(14)LEADERsensor←selectLeaderSensor(incidentVertex,Tj,i);
(15)if (LEADERsensor≠null)
(16)LinkLeaderSensor(Tj,i,LEADERsensor);
(17)incidentVertex.wasVisited←true;
(18) incidentVertex←getIncidenVertext(LEADERsensor,Gj,i);
(19)


### 5.2. Building the Spanning of Subgraph

Each subgraph or componentGj,i∈Gj-sj will build a spanning tree Tj,i taking into consideration that any node sensor in Tj,i will consume approximately same energy for transferring same notification message as others. Assume that the vertex set of subgraph Gj,i is Vj,i. The process of building the spanning tree can be managed in the following steps:(1)
Select a vertexvmin∈Vj,i with the minimum degree δGj,i.(2)
Assume thatvmin=s0,s1,…,sx. Select a node sb∈vmin (b≤x, sb is not a leader) to be the root of Tj,i and then link them; that is, if we select s0 to be the root then the link operation will be as follows: s0 is the parent of s1, s1 will be the parent of s2…, and sx-1 will be the parent of sx. Consider Lk=s0→s1→⋯sx.(3)
Select a leader nodesl from vmin and then link it to the tail of Lk.(4)
ConsiderLi=s0→s1→⋯sx→sl. If Lk is empty then li will be the root node.(5)
Markvmin as visited vertex. Then select vz as an incident of vmin such that li∈vz and li∈vmin.(6)
Repeat the steps from (2) to (4) forvz until all nodes are marked.


## 5.1. Building the Notification Tree

The main objective ofNotification Tree is to distribute the energy dissipation among the nodes of G∗sj as evenly as possible such that each node in G∗sj gets notified and consumes the same amount of energy. Each node sj in the network has aNotification TreeNTsjand its root issj.For nodesj, consider graph Gj=Vj,Ej, where Vj=sx∣sx∈G∗sj and Ej⊆Vj2 as shown in Figure 5. The operation sx∈G∗sj is true if sx∈Gi and Gi∈G∗sj. Consider sj asarticulation vertex or a cut vertex of Gj such that Gj-sj=Gj,0,Gj,1,…,Gj,i, where Gj,i is a component or subgraph of Gj.Figure 5
Notification tree.
(a)
Random 5 nodes
(b)
GroupsG∗s1
(c)
Undirect graphG1
(d)
Components ofG1-s1
(e)
N
T
s
1
(f)
N
T
s
2, NTs3, NTs4, NTs5, and NTs4When there is a notification message to be sent fromsj to its associated groups G∗sj, sj will send Gj-sj messages. That is to say, it will send a message to each component of Gj-sj. Each Gj,i∈Gj-sj will build a spanning tree Tj,i which will be attached to the root node of NTsj (Algorithm 4).Algorithm 4:Build spanning tree Tj,i for the subgraph Gj,i∈Gj-sj.
Input: Gj,i
Output: Tj,i
(1)minDegreeVertex←SelectMinDegreeVertext(Gj,i);
(2)Tj,i←null;
(3)Tj,i.Sensor←subRootSensor(minDegreeVertex,Gj,i);
(4)if (Tj,i.ID≠-1)//the link list is Empty
(5)LinkNoneLeaderSensors(Tj,i,minDegreeVertex,Gj,i);
(6)LeaderSensor←selectLeaderSensor(minDegreeVertex,LinkList);
(7)if (LeaderSensor≠null)
(8)LinkLeaderSensor(Tj,i,LeaderSensor);
(9)minDegreeVertex.wasVisited←true;
(10)incidentVertex←getIncidenVertext(LeaderSensor,Gj,i);
(11)while (incidentVertex≠null)
(12)
(13)LinkNoneLeaderSensors(Tj,i,incidentVertex,Gj,i);
(14)LEADERsensor←selectLeaderSensor(incidentVertex,Tj,i);
(15)if (LEADERsensor≠null)
(16)LinkLeaderSensor(Tj,i,LEADERsensor);
(17)incidentVertex.wasVisited←true;
(18) incidentVertex←getIncidenVertext(LEADERsensor,Gj,i);
(19)


## 5.2. Building the Spanning of Subgraph

Each subgraph or componentGj,i∈Gj-sj will build a spanning tree Tj,i taking into consideration that any node sensor in Tj,i will consume approximately same energy for transferring same notification message as others. Assume that the vertex set of subgraph Gj,i is Vj,i. The process of building the spanning tree can be managed in the following steps:(1)
Select a vertexvmin∈Vj,i with the minimum degree δGj,i.(2)
Assume thatvmin=s0,s1,…,sx. Select a node sb∈vmin (b≤x, sb is not a leader) to be the root of Tj,i and then link them; that is, if we select s0 to be the root then the link operation will be as follows: s0 is the parent of s1, s1 will be the parent of s2…, and sx-1 will be the parent of sx. Consider Lk=s0→s1→⋯sx.(3)
Select a leader nodesl from vmin and then link it to the tail of Lk.(4)
ConsiderLi=s0→s1→⋯sx→sl. If Lk is empty then li will be the root node.(5)
Markvmin as visited vertex. Then select vz as an incident of vmin such that li∈vz and li∈vmin.(6)
Repeat the steps from (2) to (4) forvz until all nodes are marked.


## 6. Avoiding Data Redundancy Mechanism

An energy-efficient avoiding reporting of redundant data helps in reducing the consumed power during communications. In the following, we will mostly focus on tracking of object such that each object is allocated to one proxy node.Forsj∈S we assume that it hasSensed Object TableSOTsj to save the information of sensed object (i.e., current position or image), and it has aNotification Messages TableNMTsj to store the notification sent/received to/from other nodes; see Figure 6. When an object oi∈M is detected by sj, sj will create a new entry in SOTsj for oi if and only if sj has no Notification record received from other sx∈G∗sj. When sj creates a new entry in SOTsj it will send anInsert notification message to G∗sj via Notification Tree NTsj to notify all nodes in G∗sj and ask them to add this notification message to their NMT tables; hence the other nodes in G∗sj will not sense oi until sj send aDelete notification message indicating that oi got out of its range. In this time all nodes in G∗sj will delete the notification messages and oi will enter any other node in G∗sj.Figure 6
Basic storage tables.
(a)
Sensed objects table
(b)
Notification message tableThe reporting process which intended to report the sensed data to the base station is aiming for selecting theproxy node immediately. The selection of proxy node can be determined based on the NMT records; for example, when there is more than only a record for oi in NMTsj=Ni,j,Ni,0,Ni,1,…,Ni,xx≠j, Ni,x is a notification messages for object oi which is detected by node sx. In this case sj will be the proxy node if it satisfied the election requirements, that is, maximum ID, residual energy, the current state, and so forth, if sj loses this round or was not elected as a proxy node it will remove oi record from SOTsj and remove Ni,j notification message from NMTsj. Worthily noted is that all G∗sj will have the same NMT. The selected proxy node will report the data and information to base station according to the reporting model explained in Section 4.Algorithm5 explained our strategy for controlling the tracking mechanism of objects such that at any time there will be one node selected as a proxy node for the mobile objects.Algorithm 5:
S
O
T
(
s
j
) and NMT(sj) controlling.
Input: A mobile object oi get in the range of sj
(1)int  x←0; //message ID
(2)if (isWithinMyRange(oi))
(3)
(4)if (oi∉NMT(sj))//no notification from other nodes
(5)
(6)mx←new  Message(); //sensed data object
(7)mx.MessageContent  ←  “data”;
(8)mx.isSent←false;
(9)if (oi∉SOT(sj))//the object has no SOT record
(10)
(11)ri←new  SensedObjRecord (); //create  new  record  in  SOT
(12)ri.MobileObject←oi;
(13)ri.MessageTable.Add(mx);
(14)SOT(sj).Add(ri);
(15)INM←new  NotificationMessage(); //create  insert  notification
(16)INM.MobileObject←oi;
(17)INM.NotificationType←Notification.Insert;
(18)INM.Source←sj;
(19)INM.Data  ←  “data”;
(20)NMT(sj).Add(INM);
(21)BroadcastInsertNotification(INM,NT(sj)); //send  the  notification  via  notification  tree
(22)sp←SelectProxyNode(oi);
(23)  if (sp≠null)
(24)
(25)  sp.MyTrackingObject.Add(oi);
(26)    sp.StartTracking();
(27)
(28)  //end if  (oi∉SOT(sj))
(29)else //the object has a SOT record
(30)
(31)   x←x+1;
(32)   UpdateSOT(oi).MessageTable.Add(mx); //update it.
(33)
(34)  //if (! isInMyNMT(mobj))
(35)//end if  oi  within my range.
(36)else //oi  get out my range.
(37)
(38)DNM←GetNotificationMessageForObject(oi); //delete
(39)if (DNM≠null)
(40)
(41)  DNM.NotificationType←Notification.Delete;
(42)   DNM.Data←  “data”;
(43)    BroadcastDeleteNotification(DNM, NT(sj)); //send  the  notification  via  notification  tree
(44)    NMT(sj).Remove(DNM);
(45)
(46)In line number 26, the functionsp.StartTracking instructs the proxy node sp to start reporting process of the sensed data. All sensed data of the objects M=o1,o2,o3,…,ox are saved in the SOTsp=r0,r1,r2,…,rx where rii≤x is a record reference for the object oi and each ri=m0,m0,m0,…,mx where mi(i≤x) is the current sensed data (see Figure 5(a)). The proxy node sp reports the records in SOTsp sequentially. The records in SOTsp will be deleted after reporting that the process is finished.


## 7. Results and Discussion

In this work, we assumed that the radio channel is symmetric such that the energy required to transmit a message ofk bits from node x to node y is the same as energy required to transmit the same size message from node y to node x for a given signal to noise ratio (SNR). We assume a simple model called (First Order Radio Model). This model discussed in [13–16]. For this model, the energy dissipation to run the radio (Eelec) is 50 nJ/bit. Eelec depends on the factors such as the digital coding, modulation, filtering, and spreading of thesignal. The free space model of transmitter amplifier is εfs=10 pJ/bit/m2 and the multipath model of transmitter amplifier is εmp=0.0013 pJ/bit/m4. Both free space and multipath models are depending on the distance to the receiver and the acceptable bit-error rate. If the distance is less than a threshold t0=εfs/εmp (meters), the free space (fs) model is used; otherwise, the multipath (mp) model is used, as shown in (13). A sensor node will consume ETxd,k of energy to transmit k bits size message over distance d and consume ERxd,k of energy to receive transmit k bits size message:(13)ETxd,k=k·Eelec+k·εfs·d2,d<t0,k·Eelec+k·εmp·d4,d≥t0,ERxk=k·Eelec.For performance evaluation, we developed a software using c# (Visual Studio 2012). We will use three different coverage schemes as shown in Figure7.Figure 7
The network topologies used to simulate the performance of GHS. The arrow indicated the position of base station (sink node). The green progress bar indicates the residual energy. Here all nodes are full charged 0.5 Joule.
(a)
Grid coverage scheme 1 [27]
(b)
Grid coverage scheme 2 [27]
(c)
Zigzag coverage scheme [28]


### 7.1. Grid Based Coverage

For grid based coverage schemes, we have selected two algorithms provided in [27], Grid Square Coverage version (1) and Grid Square Coverage version (2). Grid Square Coverage (1) algorithms have 78% coverage efficiency while Grid Square Coverage (2) has 73%.


#### 7.1.1. Grid Coverage Version (1)

Table3 shows the parameters we used to evaluate the performance of GHS in grid coverage version (1). The sensors deployed are as shown in Figure 7(a).Table 3
Simulation parameters.
Parameter
Value
Network size
500 × 500 m2
Nodes
182
Radius
25 m
Data length
1024 bits
Initial energy
0.5 Joule
E
elec
50 nJ/bit
ε
amp
0.001 pJ/bit/m2
BS location
Inside
Network topology
Grid coverage 1The evaluation results for using GHS on grid coverage version (1) are shown in Figures8 and 9. In Figure 8, the residual energy (in joule) is explained after each node of 182 nodes sent five message of size 1024 bits (five rounds). It indicates that the closed nodes to base station will die out first due to network load. As the communication range of far node is limited, the close nodes to base station will act as routers for forwarding packets that transmitted from far nodes. In addition, Figure 9 explained the dead nodes after 100, 200, and 300 rounds.Figure 8
The residual energy of nodes after five rounds. We assume that the battery of each node is 0.5 J. Network topology is grid version (1).Figure 9
The dead nodes (brown) after 100, 200, and 300 rounds using grid coverage 1 topology. The initial energy is 0.5 J/node with 50 nJ/bit dissipation to run the radio (Eelec). In each round, each sensor sends a packet of 1024 bits. The green progress bar indicates the residual energy.
(a)
1.09% of nodes die out after 100 rounds
(b)
5.4% of nodes die out after 200 rounds
(c)
7.6% of nodes die out after 300 roundsIn this coverage scheme, the number of nodes in each group is 4, which means more channels for leaders to forward data. The average number of nodes in each path (the number of hops) is4.5 when radius is 25 m. The min distance for each group is 35 m and the max distance is 49 m, that is to say, for any message (1024 bits) to be sent from node A to node B it either consumes 76288 nJ or 63744 nJ.


#### 7.1.2. Grid Coverage Version (2)

Table4 shows the parameters we used to evaluate the performance of GHS on grid coverage version (2). The network topology is shown in Figure 7(b).Table 4
Simulation parameters.
Parameter
Value
Network size
500 × 500 m2
Nodes
181
Radius
25 m
Data length
1024 bits
Initial energy
0.5 Joule
E
elec
50 nJ/bit
ε
amp
0.001 pJ/bit/m2
BS location
Inside
Network topology
Grid coverage 2In Figure10, the residual energy (in joule) is explained after each node of 181 nodes sent five messages of size 1024 bits (five rounds). Figure 11 explained the die out node after 100, 200, and 300 rounds. In this coverage scheme, the number of nodes in each group is 2, which means there are two channels for leaders to forward data. The average number of nodes in each path (the number of hops) is 6.29 when radius is 25 m. The min distance for each group is 33 m and the max distance is 36 m, that is to say, for any message (1024 bits) to be sent from node A to node B it either consumes 62996.48 nJ or 64020.48 nJ.Figure 10
The residual energy of nodes after five rounds. We assume that the battery of each node is 0.5 J. Network topology is grid version (2).Figure 11
The dead nodes (brown) after 100, 200, and 300 rounds using grid coverage 2 topology. The initial energy is 0.5 J/node with 50 nJ/bit dissipation to run the radio (Eelec). In each round, each sensor sends a packet of 1024 bits. The green progress bar indicates the residual energy.
(a)
2.2% of nodes die out after 100 rounds
(b)
6.6% of nodes die out after 200 rounds
(c)
8.8% of nodes die out after 300 rounds


### 7.2. Zigzag Based Coverage

In zigzag coverage scheme, the interest area divided into multiple zigzag patterns with multiple corners and lines segments, each node is deployed in a corner of zigzag pattern. Zigzag Pattern Scheme Deployment Algorithm expresses a very high coverage efficiency of 91%, and it expands and covers the whole interest area with minimum number of nodes, while it generates a very small coverage redundancy [28]. Table 5 shows the parameters we used to evaluate the performance of GHS on zigzag coverage sachem [16]. The network topology for zigzag is shown in Figure 5(c) (Table 5).Table 5
Simulation parameters.
Parameter
Value
Network size
500 × 500 m2
Nodes
138
Radius
25 m
Data length
1024 bits
Initial energy
0.5 Joule
E
elec
50 nJ/bit
ε
amp
0.001 pJ/bit/m2
BS location
Inside
Network topology
ZigzagIn Figure12, the residual energy (in joule) is explained after each node of 138 nodes sent five messages of size 1024 bits (five rounds). It indicates that the closed nodes to base station will die out first due to network load. Due to limited communications range of far node, the close nodes to base station will act as routers for forwarding packets that transmitted from far nodes. Figure 13 explained the amount of energy consumed by each node for the same number of rounds. In addition, Figure 14 explained the die out node after 100, 200, and 300 rounds. In this coverage scheme, the number of nodes in each group is 3, which means there are three channels for leaders to forward data. The average number of nodes in each path (the number of hops) is 4.6 when radius is 25 m. The min distance for each group is 43 m and the max distance is 44 m, that is to say, for any message (1024 bits) to be sent from node A to node B it either consumes 70605.856 nJ or 71069.7216 nJ. In Figure 15, the GHS executed 1000 rounds for the three coverage schemes depicted in Figure 7. Table 6 shows the comparisons between GHS and other well-known structures over different topologies and different initial energy.Table 6
Comparison between GHS and other well-known structures over different topologies and different initial energy.
Energy (J/node)
Coverage protocol
Nodes
Structure
Round first node dies
0.5
Grid
182
SC
67
DC
80
PTP
51
GHS
93
Zigzag
138
SC
77
DC
86
PTP
85
GHS
107
Random
100
SC
117
DC
125
PTP
121
GHS
137
1.0
Grid
182
SC
130
DC
163
PTP
102
GHS
186
Zigzag
138
SC
140
DC
170
PTP
173
GHS
190
Random
100
SC
234
DC
254
PTP
243
GHS
274
Notes:
(i) PTP = peer-to-peer, DC = dynamic clustering, and SC = static clustering.
(ii) One round means that all nodes in network take a turn to send a message, that is, one round in grid means 182 messages.Figure 12
The residual energy of nodes after five rounds. We assume that the battery of each node is 0.5 J. Network topology is zigzag.Figure 13
The consumed energy of nodes after five rounds. We assume that the battery of each node is 0.5 J. Network topology is zigzag.Figure 14
The dead nodes (brown) after 100, 200, and 300 rounds using zigzag topology. The initial energy is 0.5 J/node with 50 nJ/bit dissipation to run the radio (Eelec). In each round, each sensor sends a packet of 1024 bits. The green progress bar indicates the residual energy.
(a)
1.4% of nodes die out after 100 rounds
(b)
5% of nodes die out after 200 rounds
(c)
8.6% of nodes die out after 300 roundsFigure 15
The dead nodes (brown) of three coverage schemes after 1000 rounds of GHS, and the battery of each sensor is 0.5 J. In each round each sensor sends a packet of 1024 bits. The energy dissipation to run the radio (Eelec) is 50 nJ/bit. The green progress bar indicates the residual energy.
(a)
Grid coverage (1). 20.87% die out nodes
(b)
Grid coverage (2). 38.12% die out nodes
(c)
Zigzag coverage. 23.18% die nodes


## 7.1. Grid Based Coverage

For grid based coverage schemes, we have selected two algorithms provided in [27], Grid Square Coverage version (1) and Grid Square Coverage version (2). Grid Square Coverage (1) algorithms have 78% coverage efficiency while Grid Square Coverage (2) has 73%.


### 7.1.1. Grid Coverage Version (1)

Table3 shows the parameters we used to evaluate the performance of GHS in grid coverage version (1). The sensors deployed are as shown in Figure 7(a).Table 3
Simulation parameters.
Parameter
Value
Network size
500 × 500 m2
Nodes
182
Radius
25 m
Data length
1024 bits
Initial energy
0.5 Joule
E
elec
50 nJ/bit
ε
amp
0.001 pJ/bit/m2
BS location
Inside
Network topology
Grid coverage 1The evaluation results for using GHS on grid coverage version (1) are shown in Figures8 and 9. In Figure 8, the residual energy (in joule) is explained after each node of 182 nodes sent five message of size 1024 bits (five rounds). It indicates that the closed nodes to base station will die out first due to network load. As the communication range of far node is limited, the close nodes to base station will act as routers for forwarding packets that transmitted from far nodes. In addition, Figure 9 explained the dead nodes after 100, 200, and 300 rounds.Figure 8
The residual energy of nodes after five rounds. We assume that the battery of each node is 0.5 J. Network topology is grid version (1).Figure 9
The dead nodes (brown) after 100, 200, and 300 rounds using grid coverage 1 topology. The initial energy is 0.5 J/node with 50 nJ/bit dissipation to run the radio (Eelec). In each round, each sensor sends a packet of 1024 bits. The green progress bar indicates the residual energy.
(a)
1.09% of nodes die out after 100 rounds
(b)
5.4% of nodes die out after 200 rounds
(c)
7.6% of nodes die out after 300 roundsIn this coverage scheme, the number of nodes in each group is 4, which means more channels for leaders to forward data. The average number of nodes in each path (the number of hops) is4.5 when radius is 25 m. The min distance for each group is 35 m and the max distance is 49 m, that is to say, for any message (1024 bits) to be sent from node A to node B it either consumes 76288 nJ or 63744 nJ.


### 7.1.2. Grid Coverage Version (2)

Table4 shows the parameters we used to evaluate the performance of GHS on grid coverage version (2). The network topology is shown in Figure 7(b).Table 4
Simulation parameters.
Parameter
Value
Network size
500 × 500 m2
Nodes
181
Radius
25 m
Data length
1024 bits
Initial energy
0.5 Joule
E
elec
50 nJ/bit
ε
amp
0.001 pJ/bit/m2
BS location
Inside
Network topology
Grid coverage 2In Figure10, the residual energy (in joule) is explained after each node of 181 nodes sent five messages of size 1024 bits (five rounds). Figure 11 explained the die out node after 100, 200, and 300 rounds. In this coverage scheme, the number of nodes in each group is 2, which means there are two channels for leaders to forward data. The average number of nodes in each path (the number of hops) is 6.29 when radius is 25 m. The min distance for each group is 33 m and the max distance is 36 m, that is to say, for any message (1024 bits) to be sent from node A to node B it either consumes 62996.48 nJ or 64020.48 nJ.Figure 10
The residual energy of nodes after five rounds. We assume that the battery of each node is 0.5 J. Network topology is grid version (2).Figure 11
The dead nodes (brown) after 100, 200, and 300 rounds using grid coverage 2 topology. The initial energy is 0.5 J/node with 50 nJ/bit dissipation to run the radio (Eelec). In each round, each sensor sends a packet of 1024 bits. The green progress bar indicates the residual energy.
(a)
2.2% of nodes die out after 100 rounds
(b)
6.6% of nodes die out after 200 rounds
(c)
8.8% of nodes die out after 300 rounds


## 7.1.1. Grid Coverage Version (1)

Table3 shows the parameters we used to evaluate the performance of GHS in grid coverage version (1). The sensors deployed are as shown in Figure 7(a).Table 3
Simulation parameters.
Parameter
Value
Network size
500 × 500 m2
Nodes
182
Radius
25 m
Data length
1024 bits
Initial energy
0.5 Joule
E
elec
50 nJ/bit
ε
amp
0.001 pJ/bit/m2
BS location
Inside
Network topology
Grid coverage 1The evaluation results for using GHS on grid coverage version (1) are shown in Figures8 and 9. In Figure 8, the residual energy (in joule) is explained after each node of 182 nodes sent five message of size 1024 bits (five rounds). It indicates that the closed nodes to base station will die out first due to network load. As the communication range of far node is limited, the close nodes to base station will act as routers for forwarding packets that transmitted from far nodes. In addition, Figure 9 explained the dead nodes after 100, 200, and 300 rounds.Figure 8
The residual energy of nodes after five rounds. We assume that the battery of each node is 0.5 J. Network topology is grid version (1).Figure 9
The dead nodes (brown) after 100, 200, and 300 rounds using grid coverage 1 topology. The initial energy is 0.5 J/node with 50 nJ/bit dissipation to run the radio (Eelec). In each round, each sensor sends a packet of 1024 bits. The green progress bar indicates the residual energy.
(a)
1.09% of nodes die out after 100 rounds
(b)
5.4% of nodes die out after 200 rounds
(c)
7.6% of nodes die out after 300 roundsIn this coverage scheme, the number of nodes in each group is 4, which means more channels for leaders to forward data. The average number of nodes in each path (the number of hops) is4.5 when radius is 25 m. The min distance for each group is 35 m and the max distance is 49 m, that is to say, for any message (1024 bits) to be sent from node A to node B it either consumes 76288 nJ or 63744 nJ.


## 7.1.2. Grid Coverage Version (2)

Table4 shows the parameters we used to evaluate the performance of GHS on grid coverage version (2). The network topology is shown in Figure 7(b).Table 4
Simulation parameters.
Parameter
Value
Network size
500 × 500 m2
Nodes
181
Radius
25 m
Data length
1024 bits
Initial energy
0.5 Joule
E
elec
50 nJ/bit
ε
amp
0.001 pJ/bit/m2
BS location
Inside
Network topology
Grid coverage 2In Figure10, the residual energy (in joule) is explained after each node of 181 nodes sent five messages of size 1024 bits (five rounds). Figure 11 explained the die out node after 100, 200, and 300 rounds. In this coverage scheme, the number of nodes in each group is 2, which means there are two channels for leaders to forward data. The average number of nodes in each path (the number of hops) is 6.29 when radius is 25 m. The min distance for each group is 33 m and the max distance is 36 m, that is to say, for any message (1024 bits) to be sent from node A to node B it either consumes 62996.48 nJ or 64020.48 nJ.Figure 10
The residual energy of nodes after five rounds. We assume that the battery of each node is 0.5 J. Network topology is grid version (2).Figure 11
The dead nodes (brown) after 100, 200, and 300 rounds using grid coverage 2 topology. The initial energy is 0.5 J/node with 50 nJ/bit dissipation to run the radio (Eelec). In each round, each sensor sends a packet of 1024 bits. The green progress bar indicates the residual energy.
(a)
2.2% of nodes die out after 100 rounds
(b)
6.6% of nodes die out after 200 rounds
(c)
8.8% of nodes die out after 300 rounds


## 7.2. Zigzag Based Coverage

In zigzag coverage scheme, the interest area divided into multiple zigzag patterns with multiple corners and lines segments, each node is deployed in a corner of zigzag pattern. Zigzag Pattern Scheme Deployment Algorithm expresses a very high coverage efficiency of 91%, and it expands and covers the whole interest area with minimum number of nodes, while it generates a very small coverage redundancy [28]. Table 5 shows the parameters we used to evaluate the performance of GHS on zigzag coverage sachem [16]. The network topology for zigzag is shown in Figure 5(c) (Table 5).Table 5
Simulation parameters.
Parameter
Value
Network size
500 × 500 m2
Nodes
138
Radius
25 m
Data length
1024 bits
Initial energy
0.5 Joule
E
elec
50 nJ/bit
ε
amp
0.001 pJ/bit/m2
BS location
Inside
Network topology
ZigzagIn Figure12, the residual energy (in joule) is explained after each node of 138 nodes sent five messages of size 1024 bits (five rounds). It indicates that the closed nodes to base station will die out first due to network load. Due to limited communications range of far node, the close nodes to base station will act as routers for forwarding packets that transmitted from far nodes. Figure 13 explained the amount of energy consumed by each node for the same number of rounds. In addition, Figure 14 explained the die out node after 100, 200, and 300 rounds. In this coverage scheme, the number of nodes in each group is 3, which means there are three channels for leaders to forward data. The average number of nodes in each path (the number of hops) is 4.6 when radius is 25 m. The min distance for each group is 43 m and the max distance is 44 m, that is to say, for any message (1024 bits) to be sent from node A to node B it either consumes 70605.856 nJ or 71069.7216 nJ. In Figure 15, the GHS executed 1000 rounds for the three coverage schemes depicted in Figure 7. Table 6 shows the comparisons between GHS and other well-known structures over different topologies and different initial energy.Table 6
Comparison between GHS and other well-known structures over different topologies and different initial energy.
Energy (J/node)
Coverage protocol
Nodes
Structure
Round first node dies
0.5
Grid
182
SC
67
DC
80
PTP
51
GHS
93
Zigzag
138
SC
77
DC
86
PTP
85
GHS
107
Random
100
SC
117
DC
125
PTP
121
GHS
137
1.0
Grid
182
SC
130
DC
163
PTP
102
GHS
186
Zigzag
138
SC
140
DC
170
PTP
173
GHS
190
Random
100
SC
234
DC
254
PTP
243
GHS
274
Notes:
(i) PTP = peer-to-peer, DC = dynamic clustering, and SC = static clustering.
(ii) One round means that all nodes in network take a turn to send a message, that is, one round in grid means 182 messages.Figure 12
The residual energy of nodes after five rounds. We assume that the battery of each node is 0.5 J. Network topology is zigzag.Figure 13
The consumed energy of nodes after five rounds. We assume that the battery of each node is 0.5 J. Network topology is zigzag.Figure 14
The dead nodes (brown) after 100, 200, and 300 rounds using zigzag topology. The initial energy is 0.5 J/node with 50 nJ/bit dissipation to run the radio (Eelec). In each round, each sensor sends a packet of 1024 bits. The green progress bar indicates the residual energy.
(a)
1.4% of nodes die out after 100 rounds
(b)
5% of nodes die out after 200 rounds
(c)
8.6% of nodes die out after 300 roundsFigure 15
The dead nodes (brown) of three coverage schemes after 1000 rounds of GHS, and the battery of each sensor is 0.5 J. In each round each sensor sends a packet of 1024 bits. The energy dissipation to run the radio (Eelec) is 50 nJ/bit. The green progress bar indicates the residual energy.
(a)
Grid coverage (1). 20.87% die out nodes
(b)
Grid coverage (2). 38.12% die out nodes
(c)
Zigzag coverage. 23.18% die nodes


## 8. Conclusion and Further Works

This paper intended to develop aSensors Grouping Hierarchy Structure (GHS) for partitioning the nodes into groups according to themaximum overlapped regions in the field. A group of sensors contain multiple number of nodes and a multiple number of leaders, and each node can belong to more than one group. We assumed that the interest field is covered with the minimum number of nodes such that the overlapped between the nodes is minimized and the nodes are expanded to cover the interested field completely. Thisstructure enhances the collaborative, dynamic, distributive computing and communication of the system, and it maximizes the lifespan of nodes by minimizing energy consumption, balancing energy, and generating a little redundant data.For further research, we plan to extend our structure by studying the influence of nodes quick movement in the field. And we will study the object tracking intensively using this structure. The researchers are very welcomed to develop energy efficient data routing algorithms and objects tracking algorithms using GHS.



---

*Source: 650519-2015-08-16.xml*