Sensors Grouping Hierarchy Structure for Wireless Sensor Network

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.

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 Figure 1, 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.

This paper intended to develop and design a grouping algorithm to be used for partitioning the nodes into groups according to the maximum overlapped regions in the field. We will see the impact of this model in

• (i)

data routing and energy saving (Section 4),

(ii)

object tracking and energy balancing (Section 5),

(iii)

avoiding data redundancy (Section 6).

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 Section 2, 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 their geographical 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 8 maximum 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.

In 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 of n sensors is represented by a square matrix $(n\times n)$ . Consider

$$\begin{array}{cc}& A^{\ast }={\left[\begin{array}{cc}\begin{array}{c}\begin{array}{c}\mathrm{1}\\ \mathrm{1}\end{array}\\ ⋮\\ \begin{array}{c}\mathrm{0}\\ \mathrm{0}\end{array}\end{array}& \begin{array}{ccc}\begin{array}{c}\begin{array}{c}\mathrm{1}\\ \mathrm{1}\end{array}\\ ⋮\\ \begin{array}{c}\mathrm{1}\\ \mathrm{0}\end{array}\end{array}& \cdots & \begin{array}{c}\begin{array}{c}\mathrm{0}\\ \mathrm{0}\end{array}\\ ⋮\\ \begin{array}{c}\mathrm{1}\\ \mathrm{1}\end{array}\end{array}\end{array}\end{array}\right]}_{n\times n},\\ a_{ij}=\left\{\begin{array}{cc}\mathrm{1},\hfill & s_i\hspace{0.17em}\hspace{0.17em}\text{and}\hspace{0.17em}\hspace{0.17em}{s}_j\hspace{0.17em}\hspace{0.17em}\text{are\hspace{0.17em}\hspace{0.17em}overlapped,}\hfill \\ \mathrm{1},\hfill & i=j,\hfill \\ \mathrm{0},\hfill & s_i\hspace{0.17em}\hspace{0.17em}\text{and}\hspace{0.17em}\hspace{0.17em}{s}_j\hspace{0.17em}\hspace{0.17em}\text{are}\hspace{0.17em}\hspace{0.17em}\text{not}\hspace{0.17em}\hspace{0.17em}\text{overlapped.}\hfill \end{array}\right.\end{array}$$

(1)

For example, the network in Figure 2 is represented by a square matrix (12 × 12):

$$\begin{array}{cc}& A^{\ast }=\left[\begin{array}{cccccccccccc}\mathrm{1}& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ \mathrm{1}& 1& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ \mathrm{1}& 1& 1& 1& 0& 0& 0& 0& 1& 0& 0& 0\\ \mathrm{1}& 1& 1& 1& 0& 0& 0& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 1& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 1& 0& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 0& 0& 0& 1& 1& 1& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 0& 1& 0& 0& 0& 0& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 1\end{array}\right].\end{array}$$

(2)

We can find the maximum covered regions by partitioning $A^{\ast }$ into square submatrices $\left\{A_{\mathrm{1}},A_{\mathrm{2}},A_{\mathrm{3}},\dots \right\}$ such that all elements of submatrix $a_{ij}=\mathrm{1}$ , as well as the subsquare matrix, contain the maximum 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:

$$\begin{array}{cc}& A_{\mathrm{1}}={\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\end{array}\right]}_{g_{\mathrm{1}}=\left(\mathrm{1,2},\mathrm{3,4}\right)},\\ A_{\mathrm{2}}={\left[\begin{array}{ccc}\mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}& \mathrm{1}\end{array}\right]}_{g_{\mathrm{2}}=\left(\mathrm{3,4},\mathrm{9}\right)},\\ A_{\mathrm{3}}={\left[\begin{array}{ccc}\mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}& \mathrm{1}\end{array}\right]}_{g_{\mathrm{3}}=\left(\mathrm{4,8},\mathrm{9}\right)},\\ A_{\mathrm{4}}={\left[\begin{array}{cc}\mathrm{1}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}\end{array}\right]}_{g_{\mathrm{4}}=\left(\mathrm{6,8}\right)},\\ A_{\mathrm{5}}={\left[\begin{array}{cc}\mathrm{1}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}\end{array}\right]}_{g_{\mathrm{5}}=\left(\mathrm{9,10}\right)},\\ A_{\mathrm{6}}={\left[\begin{array}{ccc}\mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}& \mathrm{1}\end{array}\right]}_{g_{\mathrm{6}}=\left(\mathrm{10,11,12}\right)},\\ A_{\mathrm{7}}={\left[\begin{array}{ccc}\mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}& \mathrm{1}\end{array}\right]}_{g_{\mathrm{7}}=\left(\mathrm{5,10,11}\right)},\\ A_{\mathrm{8}}={\left[\begin{array}{cc}\mathrm{1}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}\end{array}\right]}_{g_{\mathrm{8}}=\left(\mathrm{5,7}\right)}.\end{array}$$

(3)

If WSN is connected then $A^{\ast }\left(n\times n\right)$ can be partitioned into square submatrices $\left\{A_{\mathrm{1}},A_{\mathrm{2}},A_{\mathrm{3}},\dots ,A_i\right\}$ , where i is an integer and $\mathrm{1}\le i\le n-\mathrm{1}$ .

We divide the nodes into a set of groups dynamically such that $G^{\ast }=\left\{G^i,G^j,G^k,\dots \right\}$ , where $i,j$ and k are integers indicating the number of sensors in the groups $G^i$ , $G^j$ , and $G^k$ , respectively. Note that the term of groups is different from the term clusters.

A group $G^k\in G^{\ast }$ contains $\mathrm{1}+k\left(k-\mathrm{1}\right)$ subareas and among them there will be one area which is $k\text{-}covered$ , k areas which are $1\text{-}covered$ , k areas which are $2\text{-}covered\dots$ , and k areas which are $k-1$   covered. Note that when an object moves in $x\text{-}covered$ area ( $x>1,x\in \mathbb{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\in G^k$ there are $1+k(k-1)/2$ subareas, among them one area is   $k\text{-}covered$ , 1  area is   $1\text{-}covered$ , 2 areas are   $2\text{-}covered$ , 3 areas are   $3\text{-}covered\dots$ , and   $k-1$ areas are   $k-1$    $covered$ ; that is, see Figure 3.

Figure 3

A group $G^{\mathrm{4}}$ .

A group $G^k\in G^{\ast }$ contains $R\left(G^k\right)=\mathrm{1}+k\left(k-\mathrm{1}\right)$ regions (i.e., Figure 3(b)). We can count the $R\left(G^k\right)$ easily by considering the number of regions in $G^k$ with no repetition; that is to say,

$$\begin{array}{cc}& R\left(G^k\right)={\displaystyle \sum }_{j=\mathrm{0}}^{k}R\left(s_j\right),\end{array}$$

(4)

where $R\left(s_j\right)$ is the number of regions within the range of $s_j$ , and it is easy to see that the number of areas inside the range of node $s_j$ is satisfying the recursive relation:

$$\begin{array}{cc}& R\left(s_j\in G^k\right)=\left\{\begin{array}{c}f\left(k\right)=k+f\left(k-\mathrm{1}\right)-\mathrm{1},\\ k\ge \mathrm{1},\\ f\left(\mathrm{1}\right)=\mathrm{1}.\end{array}\right.\end{array}$$

(5)

We can solve this equation using generation functions and obtain

$$\begin{array}{cc}& R\left(s_j\in G^k\right)=\mathrm{1}+\frac{k\left(k-\mathrm{1}\right)}{\mathrm{2}},\\ R\left(s_j\in G^k\right)=\mathrm{1}+\left(\begin{array}{c}k\\ \mathrm{2}\end{array}\right).\end{array}$$

(6)

By removing the repetition from (4), we can get

$$\begin{array}{ll}R\left(G^k\right)& =\mathrm{1}+\left(\begin{array}{l}k\\ \mathrm{2}\end{array}\right)+\left(k-\mathrm{1}\right)+\left(k-\mathrm{2}\right)\\ & +\cdots \left(k-\left(k-\mathrm{1}\right)\right),\\ R\left(G^k\right)& =\mathrm{1}+\left(\begin{array}{l}k\\ \mathrm{2}\end{array}\right)+{\displaystyle \sum }_{i=\mathrm{1}}^{k-\mathrm{1}}\left(k-i\right)\\ & =\mathrm{1}+\frac{k!}{\mathrm{2}!\left(k-\mathrm{2}\right)!}+\frac{k\left(k-\mathrm{1}\right)}{\mathrm{2}}\\ & =\mathrm{1}+\frac{k\left(k-\mathrm{1}\right)}{\mathrm{2}}+\frac{k\left(k-\mathrm{1}\right)}{\mathrm{2}}=\mathrm{1}+k\left(k-\mathrm{1}\right).\end{array}$$

(7)

Among $R\left(G^k\right)$ there will be one area which is $k\text{-}covered$ , k areas which are $\mathrm{1}\text{-}covered$ , k areas which are $\mathrm{2}\text{-}covered\dots$ , and k areas which are $k-\mathrm{1}\mathrm{\hspace{0.17em}\hspace{0.17em}}covered$ . Let $C_{x,k}$ ( $x\le k$ ) be the notation for $x\text{-}covered$ region in $R\left(G^k\right)$ and let $\Phi \left(C_{x,k}\right)$ be the number of $C_{x,k}$ in $R\left(G^k\right)$ ; hence $\Phi \left(C_{0,k}\right)=0$ , $\Phi \left(C_{k,k}\right)=1$ , and, generally, $\Phi \left(C_{x,k}\right)=k$ , where $\left(k-1\ge x\ge 1\right)$ and then it is easy to see that

$$\begin{array}{ll}R\left(G^k\right)& =\Phi \left(C_{\mathrm{0},k}\right)+\Phi \left(C_{\mathrm{1},k}\right)+\Phi \left(C_{\mathrm{2},k}\right)+\cdots \Phi \left(C_{k,k}\right)\\ & ={\displaystyle \sum }_{i=\mathrm{0}}^k\Phi \left(C_{i,k}\right)=\mathrm{0}+k+k+\cdots +\mathrm{1}\\ & =\mathrm{1}+k\left(k-\mathrm{1}\right).\end{array}$$

(8)

Furthermore, among the $R\left(s_j\in G^k\right)$ there will be one area which is $k\text{-}covered$ , 1 area which is $1\text{-}covered$ , 2 areas which are $2\text{-}covered$ , 3 areas which are $3\text{-}covered\dots$ , and $k-1$ areas which are $k-1\hspace{0.17em}\hspace{0.17em}covered$ ; that is, see Figure 3(a). We denoted to the $x\text{-}covered$ regions in the range of node $s_j$ by $c_{x,j}$ ( $x\ge 0$ ), and let $\theta \left(c_{x,j}\right)$ be the number of $c_{x,j}$ regions; then, for any $s_j\in G^k$ , the $\theta \left(c_{i,j}\right)=i$ , where   $\left(k-1\ge i\ge 0\right)$ . We can obtain that $\theta \left(c_{0,j}\right)=0$ and $\theta \left(c_{k,j}\right)=1$ . It is obvious that

$$\begin{array}{ll}R\left(s_j\in G^k\right)& =\theta \left(c_{\mathrm{0},j}\right)+\theta \left(c_{\mathrm{1},j}\right)+\theta \left(c_{\mathrm{2},j}\right)+\cdots \theta \left(c_{k,j}\right)\\ & =\theta \left(c_{k,j}\right)+{\displaystyle \sum }_{i=\mathrm{0}}^{k-\mathrm{1}}\theta \left(c_{i,j}\right)\\ & =\theta \left(c_{k,j}\right)+\mathrm{0}+\mathrm{1}+\mathrm{2}+\mathrm{3}+\cdots +\left(k-\mathrm{1}\right)\\ & =\mathrm{1}+\frac{k\left(k-\mathrm{1}\right)}{\mathrm{2}}.\end{array}$$

(9)

Therefore, we can obtain the number of regions $R\left(s_j\in G^{\ast }\left(s_j\right)\right)$ , where $G^{\ast }\left(s_j\right)$ is the set of associated groups of $s_j$ such that $G^{\ast }\left(s_j\right)=\left\{G^x\hspace{0.17em}|\hspace{0.17em}{G}^x\in G^{\ast }\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{\hspace{0.17em}\hspace{0.17em}}{s}_j\in G^x\right\}$ . Let ${\rm Y}=\left|G^{\ast }\left(s_j\right)\right|$ ; then

$$\begin{array}{ll}R\left(s_j\in G^{\ast }\left(s_j\right)\right)& \le \left({\displaystyle \sum }_{G^x\in G^{\ast }\left(s_j\right)}R\left(s_j\in G^x\right)\right)\\ & -\left({\rm Y}-\mathrm{1}\right).\end{array}$$

(10)

Any object $o_i\in M$ moves in a group $G^k\in G^{\ast }$ , its location should be detected within the group range with respect to the Probability space $\Omega (G^k\in G^{\ast })=\left\{C_{1,k},C_{2,k},\dots ,C_{k,k}\right\}$ . However, any object $o_i\in M$ moves in the range of node $s_j\in G^{\ast }\left(s_j\right)$ ; its location should be detected with respect to the Probability space $\Omega \left(s_j\in G^{\ast }\left(s_j\right)\right)=\left\{c_{1,j},c_{2,j},\dots ,c_{k,j}\right\}$ .

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 a distributed 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 the maximum 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 of $$s_i$$ . Here we call V the vector of sensor.
	$$\left|V_i\right|$$ Is the number of sensor inside $$V_i$$ .
	$$D=\sqrt{{(x_{s_i}-x_{s_j})}^{\mathrm{2}}+{(y_{s_i}-y_{s_j})}^{\mathrm{2}}}$$
	$$\forall s_j\in S$$   do:
	{
	if ( $$r_i$$ + $$r_j$$ < D) do:
	$$V_i\_add(s_j)$$ ;
	}
$$N_i$$	The list of neighbor vectors for $$s_i$$ .
	$$\forall s_j\in V_i$$   do:
	find   $$V_j$$   and then add   $$V_j$$   to   $$N_i$$   by calling:
	$$N_i\_add(V_j)$$ .
	That is to find the vector for each sensor $$s_j$$ such that $$s_j\in V_i$$    $$i\ne j$$ .
	The number of vectors in $$N_i$$ is denoted by $$\left.\right|N_i\left|\right.$$ .
$$F_i$$	The list of filtered neighbor vectors for $$s_i$$ . The filtering process is running as:
	$$\forall V_a\in N_i$$   do:
	{
	$$V_x\leftarrow null$$ ;
	$$\forall s_c\in V_a$$   do:
	{
	if ( $$s_c\in V_i$$ ) $$do$$ :
	{
	$$V_x$$ . $$add(s_c)$$ ;
	}
	}
	$$F_i\_add(V_x)$$
	}
	That is to say, the sensor in the $$N_i$$ will be add to $$F_i$$ if and only if they are belong to $$V_i$$ , otherwise they will be ignored. $$\left.\right|F_i\left|\right.$$ is the number of vectors inside $$F_i$$ .
$$G^{\ast }(s_j)$$	The associated groups of $$s_i$$ , such that $$G^{\ast }(s_j)=\{G^x\hspace{0.17em}|\hspace{0.17em}{G}^x\in G^{\ast }\hspace{0.17em}\hspace{0.17em}\text{and}\hspace{0.17em}\hspace{0.17em}{s}_j\in G^x\}$$ .
$$F_i[n]$$	Get the filtered vector with index n.

Algorithm 1: Grouping algorithm.

Find $$G^{\ast }(s_i)$$

Input: $$s_i,S$$

Output: $$G^{\ast }(s_i)$$   the associated groups of $$s_i$$

(1) $$V_i\leftarrow s_i$$ .Vector

(2) for (int   $$k\leftarrow \mathrm{0}$$ ; $$k<\left.\right|F_i\left|\right.$$ ; k++)

(3) {

(4)   $$V_k\leftarrow F_i[k]$$ ;

(5)   $$s_k\leftarrow V_i[k]$$ ;

(6)   if ( $$\left.\right|V_k\left|\right.=\mathrm{2}$$ )

(7)    {

(8)      $$G^k\leftarrow V_k$$

(9)      $$G^{\ast }(s_i)$$ += $$G^k$$

(10)   }

(11)  else

(12)   {

(13)      for (int $$m\leftarrow k+\mathrm{1}$$ ; $$m<\left.\right|F_i\left|\right.$$ ; m++)

(14)      {

(15)        $$V_m\leftarrow F_i\left[m\right]$$ ;

(16)        if ( $$s_k\in V_m$$ )

(17)        {

(18)          $$G^{\left|V_k\cap V_m\right|}\leftarrow V_k\cap V_m$$

(19)          $$G^{\ast }(s_i)$$ += $$G^{\left|V_k\cap V_m\right|}$$

(20)        }

(21)       }

(22)     }

(23) }

Algorithm 1 shows how the sensor node $s_i$ aware its associated groups $G^{\ast }\left(s_j\right)=\left\{G^x\hspace{0.17em}|\hspace{0.17em}{G}^x\in G^{\ast }\hspace{0.17em}\hspace{0.17em}\mathrm{a}\mathrm{n}\mathrm{d}\hspace{0.17em}\hspace{0.17em}{s}_j\in G^x\right\}$ .

By analyzing Algorithm 1, we can predict the resources (i.e., memory, communication bandwidth, and energy) it requires. Assume that $n=\left|F_i\right|$ is the input size (the number of filtered vectors); then it is easy to compute the time complexity of Algorithm 1:

$$\begin{array}{cc}& T\left(n\right)=\left(n-\mathrm{1}\right)+\left(n-\mathrm{2}\right)+\left(n-\mathrm{3}\right)+\cdots +\mathrm{3}+\mathrm{2}+\mathrm{1},\\ T\left(n\right)={\displaystyle \sum }_{j=\mathrm{1}}^n\left(n-j\right),\\ T\left(n\right)=\frac{\mathrm{1}}{\mathrm{2}}n\left(n-\mathrm{1}\right).\end{array}$$

(11)

The worst-case running time is

$$\begin{array}{cc}& T\left(n\right)=\theta \left(n^{\mathrm{2}}\right).\end{array}$$

(12)

3. Network Model

We model the Grouped based network using a weighted graph G, where graph vertices correspond to groups and graph edges correspond to leader 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 a statics Graph $G=\left(V,E,\mu \right)$ 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 $\mu :E\to {\mathbb{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 $\mu \left(v,v\right)=\mathrm{0}$ for any node $v\in 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 Algorithm 1 such that $G^{\ast }=\left\{G^i,G^j,G^k,\dots \right\}$ . A group $G^x\in G^{\ast }$ contains a number of sensors, that is, $G^x=\left\{s_1,s_2,\dots ,s_v\right\}$ , $\left|G^x\right|=v$ , and multiple number of leaders. The set of groups $G^{\ast }\left(s_j\right)$ is called the associated groups of $s_j$ , such that $G^{\ast }\left(s_j\right)=\left\{G^x\hspace{0.17em}|\hspace{0.17em}{G}^x\in G^{\ast }\hspace{0.17em}\hspace{0.17em}\mathrm{a}\mathrm{n}\mathrm{d}\hspace{0.17em}\hspace{0.17em}{s}_j\in G^x\right\}$ . 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 (Figure 2).

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 (Algorithm 2) 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: $$s_i$$ is the Source Node

Output: send data to BS directly, or forward data via multi-hop path.

(1) $$\mathbf{D}\mathbf{a}\mathbf{t}\mathbf{a}\mathbf{R}\mathbf{o}\mathbf{u}\mathbf{t}\mathbf{i}\mathbf{n}\mathbf{g}$$ ( $$s_i$$ , Message msg )

(2) {

(3)  TargetGroup ←  GetMinDistanceGroupFor( $$s_i$$ );

(4)   $$s_t\leftarrow$$ MinDistanceSensor(TargetGroup); // $$s_t$$ is the target node

(5)  if ( $$s_t$$ .ID ≠ SinkNode.ID)

(6)   {

(7)     $$s_i$$ .SendData( $$s_t$$ );

(8)       $$s_t$$ .ReceiveData( $$s_i$$ );

(9)      DataRouting( $$s_t$$ , msg );

(10)    }

(11)     else

(12)    {

(13)      $$s_i$$ .SendData(SinkNode);

(14)     SinkNode.ReceiveData( $$s_i$$ );

(15)    }

(16) }

Figure 4

Grouped based data routing.

4.1. Energy Saving during Data Routing

The grouping model provided an efficient energy management during communication. Consider group $G^4=\left\{s_1,s_2,s_3,s_4\right\}$ of network depicted in Figure 2, and assume that $s_1$ 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 $s_1$ 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 $s_2$ then the consumed energy to transmit the packet from $s_1$ to $s_2$ is wasted. Our grouping model avoided such situations as below.

• (1)

In the same group, the none-leader to none-leader routing always 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, the leader to leader routing sometime leads to wastage of energy consumption.

(3)

In the same group, the leader to none-leader routing always leads to wastage of energy consumption.

The logical structure of grouping model for network deployed in Figure 2 is explained in Figure 4(b). When a none-leader node has data to send, it just selects one of the leaders in the group and then transmits data to the selected leader. The leader can be selected upon three main parameters:

• (1)

the residual energy of leader (i.e., the leader with more energy win),

(2)

the distance to source node (i.e., the nearest leader win),

(3)

the current state of leader (i.e., busy or free).

5. Object Tracking and Energy Balancing

Consider a set of m mobile objects $M=\left\{o_1,o_2,o_3,\dots ,o_m\right\}$ moving randomly in the range of set of n none-mobile nodes $S=\left\{s_1,s_2,s_3,\dots ,s_n\right\}$ . The nodes of network are partitioned into groups dynamically such that $G^{\ast }=\left\{G^i,G^j,G^k,\dots \right\}$ . We assume that any node $s_j\in S$ is aware of the associated groups to which it belongs, such that $G^{\ast }\left(s_j\right)=\left\{G^x\hspace{0.17em}|\hspace{0.17em}{G}^x\in G^{\ast }\hspace{0.17em}\hspace{0.17em}\mathrm{a}\mathrm{n}\mathrm{d}\hspace{0.17em}\hspace{0.17em}{s}_j\in G^x\right\}$ . Regarding energy balancing, when there is a notification message (i.e., Insert, Rescue, and Delete) to be sent from $s_j$ to its associated groups $G^{\ast }\left(s_j\right)$ , and $s_j$ will not be sent to all nodes in $G^{\ast }\left(s_j\right)$ separately. However, $s_j$ build a Notification Tree $NT\left(s_j\right)$ to manage the notifications (Algorithm 3), which will be sent to all nodes in $G^{\ast }\left(s_j\right)$ with respect to energy saving of $s_j$ and energy balancing of $G^{\ast }\left(s_j\right)$ . The Notification Tree ensures that all nodes in $G^{\ast }\left(s_j\right)$ will consume approximately the same amount of energy during sending notifications.

Algorithm 3: Build the Notification Tree.

Input : $${\mathit{s}}_{\mathit{j}}$$

Output : $$\mathit{N}\mathit{T}$$ ( $${\mathit{s}}_{\mathit{j}}$$ )

(1) $$Root\leftarrow s_j$$ ;

(2)   $$G_j\leftarrow (V_j,E_j)$$ // $$V_j=\{s_x\hspace{0.17em}|\hspace{0.17em}{s}_x\in G^{\ast }(s_j)\}$$   and   $$E_j\subseteq [V_j{]}^{\mathit{2}}$$

(3)    $${G_{j,i}\leftarrow G}_j-s_j$$ //{ $$G_{j,\mathit{0}},G_{j,\mathit{1}},\dots ,G_{j,i}$$ }  subgraphs

(4)  for (int   $$i\leftarrow \mathit{0}$$ ; $$i<\left.\right|G_{j,i}\left|\right.$$ ; i++)

(5)  {

(6)    $$T_{j,i}\leftarrow BuidSpanningTree(G_{j,i})$$ //build the spanning tree for each subgraph.

(7)   Root.childern.add( $$T_{j,i}$$ )

(8)  }

5.1. Building the Notification Tree

The main objective of Notification Tree is to distribute the energy dissipation among the nodes of $G^{\ast }\left(s_j\right)$ as evenly as possible such that each node in $G^{\ast }\left(s_j\right)$ gets notified and consumes the same amount of energy. Each node $s_j$ in the network has a Notification Tree $NT\left(s_j\right)$ and its root is $s_j$ .

For node $s_j$ , consider graph $G_j=\left(V_j,E_j\right)$ , where $V_j=\left\{s_x\hspace{0.17em}|\hspace{0.17em}{s}_x\in G^{\ast }\left(s_j\right)\right\}$ and $E_j\subseteq {\left[V_j\right]}^{\mathrm{2}}$ as shown in Figure 5. The operation $s_x\in G^{\ast }\left(s_j\right)$ is true if $s_x\in G^i$ and $G^i\in G^{\ast }\left(s_j\right)$ . Consider $s_j$ as articulation vertex or a cut vertex of $G_j$ such that $G_j-s_j=\left\{G_{j,\mathrm{0}},G_{j,\mathrm{1}},\dots ,G_{j,i}\right\}$ , where $G_{j,i}$ is a component or subgraph of $G_j$ .

Figure 5

Notification tree.

When there is a notification message to be sent from $s_j$ to its associated groups $G^{\ast }\left(s_j\right)$ , $s_j$ will send $\left|G_j-s_j\right|$ messages. That is to say, it will send a message to each component of $G_j-s_j$ . Each $G_{j,i}\in G_j-s_j$ will build a spanning tree $T_{j,i}$ which will be attached to the root node of $NT\left(s_j\right)$ (Algorithm 4).

Algorithm 4: Build spanning tree $$T_{j,i}$$ for the subgraph $$G_{j,i}\in G_j-s_j$$ .

Input: $${\mathit{G}}_{\mathit{j},\mathit{i}}$$

Output: $${\mathit{T}}_{\mathit{j},\mathit{i}}$$

(1) $$minDegreeVertex\leftarrow SelectMinDegreeVertext(G_{j,i})$$ ;

(2)   $$T_{j,i}\leftarrow null$$ ;

(3)   $$T_{j,i}$$ . $$Sensor\leftarrow subRootSensor(minDegreeVertex,G_{j,i})$$ ;

(4) $$if$$ ( $$T_{j,i}$$ . $$ID\ne -\mathrm{1})$$ // the link list is Empty

(5)   $$LinkNoneLeaderSensors(T_{j,i},minDegreeVertex,G_{j,i})$$ ;

(6) $$LeaderSensor\leftarrow selectLeaderSensor(minDegreeVertex,LinkList)$$ ;

(7) $$if$$ ( $$LeaderSensor\ne null)$$

(8) $$LinkLeaderSensor(T_{j,i},LeaderSensor)$$ ;

(9) $$minDegreeVertex$$ . $$wasVisited\leftarrow true$$ ;

(10) $$incidentVertex\leftarrow getIncidenVertext(LeaderSensor,G_{j,i})$$ ;

(11) $$while$$ ( $$incidentVertex\ne null)$$

(12) {

(13)  $$LinkNoneLeaderSensors(T_{j,i},incidentVertex,G_{j,i})$$ ;

(14)  $$LEADERsensor\leftarrow selectLeaderSensor(incidentVertex,T_{j,i})$$ ;

(15)  $$if$$ ( $$LEADERsensor\ne null)$$

(16)  $$LinkLeaderSensor(T_{j,i},LEADERsensor)$$ ;

(17)  $$incidentVertex$$ . $$wasVisited\leftarrow true$$ ;

(18)   $$incidentVertex\leftarrow getIncidenVertext(LEADERsensor,G_{j,i})$$ ;

(19) }

5.2. Building the Spanning of Subgraph

Each subgraph or component $G_{j,i}\in G_j-s_j$ will build a spanning tree $T_{j,i}$ taking into consideration that any node sensor in $T_{j,i}$ will consume approximately same energy for transferring same notification message as others. Assume that the vertex set of subgraph $G_{j,i}$ is $V_{j,i}$ . The process of building the spanning tree can be managed in the following steps:

• (1)

Select a vertex $v_{\mathrm{m}\mathrm{i}\mathrm{n}}\in V_{j,i}$ with the minimum degree $\delta \left(G_{j,i}\right)$ .

(2)

Assume that $v_{\mathrm{m}\mathrm{i}\mathrm{n}}=\left\{s_0,s_1,\dots ,s_x\right\}$ . Select a node $s_b\in v_{\mathrm{m}\mathrm{i}\mathrm{n}}$ ( $b\le x$ , $s_b$ is not a leader) to be the root of $T_{j,i}$ and then link them; that is, if we select $s_0$ to be the root then the link operation will be as follows: $s_0$ is the parent of $s_1$ , $s_1$ will be the parent of $s_2$ …, and $s_{x-1}$ will be the parent of $s_x$ . Consider $L_k=\left\{s_0\to s_1\to \cdots s_x\right\}$ .

(3)

Select a leader node $s_l$ from $v_{\mathrm{m}\mathrm{i}\mathrm{n}}$ and then link it to the tail of $L_k$ .

(4)

Consider $L_i=\left\{s_{\mathrm{0}}\to s_{\mathrm{1}}\to \cdots s_x\to s_l\right\}$ . If $L_k$ is empty then $l_i$ will be the root node.

(5)

Mark $v_{\mathrm{m}\mathrm{i}\mathrm{n}}$ as visited vertex. Then select $v_z$ as an incident of $v_{\mathrm{m}\mathrm{i}\mathrm{n}}$ such that $l_i\in v_z$ and $l_i\in v_{\mathrm{m}\mathrm{i}\mathrm{n}}$ .

(6)

Repeat the steps from (2) to (4) for $v_z$ 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.

For $s_j\in S$ we assume that it has Sensed Object Table $SOT\left(s_j\right)$ to save the information of sensed object (i.e., current position or image), and it has a Notification Messages Table $NMT\left(s_j\right)$ to store the notification sent/received to/from other nodes; see Figure 6. When an object $o_i\in M$ is detected by $s_j$ , $s_j$ will create a new entry in $SOT\left(s_j\right)$ for $o_i$ if and only if $s_j$ has no Notification record received from other $s_x\in G^{\ast }\left(s_j\right)$ . When $s_j$ creates a new entry in $SOT\left(s_j\right)$ it will send an Insert notification message to $G^{\ast }\left(s_j\right)$ via Notification Tree $NT\left(s_j\right)$ to notify all nodes in $G^{\ast }\left(s_j\right)$ and ask them to add this notification message to their $NMT$ tables; hence the other nodes in $G^{\ast }\left(s_j\right)$ will not sense $o_i$ until $s_j$ send a Delete notification message indicating that $o_i$ got out of its range. In this time all nodes in $G^{\ast }\left(s_j\right)$ will delete the notification messages and $o_i$ will enter any other node in $G^{\ast }\left(s_j\right)$ .

Figure 6

Basic storage tables.

The reporting process which intended to report the sensed data to the base station is aiming for selecting the proxy 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 $o_i$ in $NMT\left(s_j\right)=\left\{N_{i,j},N_{i,0},N_{i,1},\dots ,N_{i,x}\right\}\hspace{0.17em}\hspace{0.17em}x\ne j$ , $N_{i,x}$ is a notification messages for object $o_i$ which is detected by node $s_x$ . In this case $s_j$ will be the proxy node if it satisfied the election requirements, that is, maximum ID, residual energy, the current state, and so forth, if $s_j$ loses this round or was not elected as a proxy node it will remove $o_i$ record from $SOT\left(s_j\right)$ and remove $N_{i,j}$ notification message from $NMT\left(s_j\right)$ . Worthily noted is that all $G^{\ast }\left(s_j\right)$ 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.

Algorithm 5 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: $$SOT(s_j)$$ and $$NMT(s_j)$$ controlling.

Input: A mobile object $$o_i$$ get in the range of $$s_j$$

(1)  int   $$x\leftarrow \mathit{0}$$ ; //message ID

(2) if ( $$isWithinMyRange$$ ( $$o_i$$ ))

(3) {

(4)   if ( $$o_i\notin NMT(s_j)$$ )//no notification from other nodes

(5)  {

(6)    $$m_x\leftarrow new$$    Message (); //sensed data object

(7)    $$m_x$$ .MessageContent  ←  “data”;

(8)    $$m_x$$ . $$isSent\leftarrow false$$ ;

(9)    if ( $$o_i\notin SOT(s_j)$$ )//the object has no SOT record

(10)   {

(11)     $$r_i\leftarrow new$$    SensedObjRecord (); // create  new  record  in  SOT

(12)     $$r_i$$ . $$MobileObject\leftarrow o_i$$ ;

(13)     $$r_i$$ .MessageTable.Add( $$m_x$$ );

(14)    $$SOT(s_j)$$ . Add ( $$r_i$$ );

(15)     $$INM\leftarrow new$$    NotificationMessage (); //create  insert  notification

(16)    INM. $$\mathrm{MobileO}bject\leftarrow o_i$$ ;

(17)    INM. $$\mathrm{NotificationT}ype\leftarrow Notification$$ .Insert;

(18)    $$INM$$ . $$Source\leftarrow s_j$$ ;

(19)    $$INM$$ . $$Data$$   ←  “data”;

(20)    $$NMT(s_j)$$ . $$Add(INM)$$ ;

(21)     BroadcastInsertNotification $$(INM,NT(s_j))$$ ; //send  the  notification  via  notification  tree

(22)     $$s_p\leftarrow SelectProxyNode(o_i)$$ ;

(23)       if ( $$s_p\ne null)$$

(24)      {

(25)        $$s_p$$ . $$MyTrackingObject$$ . $$Add(o_i)$$ ;

(26)          $$s_p$$ . $$StartTracking()$$ ;

(27)      }

(28)    }//end if   $$(o_i\notin SOT(s_j))$$

(29)   else //the object has a SOT record

(30)    {

(31)      $$x\leftarrow x+\mathit{1}$$ ;

(32)      $$UpdateSOT(o_i)$$ . $$MessageTable$$ . $$Add(m_x)$$ ; //update it.

(33)    }

(34)   }//if (! isInMyNMT(mobj))

(35) }//end if   $$o_i$$   within my range.

(36) else // $$o_i$$   get out my range.

(37) {

(38)   $$DNM\leftarrow GetNotificationMessageForObject(o_i)$$ ; //delete

(39)   if ( $$DNM\ne null)$$

(40)   {

(41)     $$DNM.NotificationType\leftarrow Notification.Delete$$ ;

(42)      $$DNM.Data\leftarrow$$   “data”;

(43)       BroadcastDeleteNotification (DNM, NT( $$s_j$$ )); //send  the  notification  via  notification  tree

(44)       $$NMT(s_j)$$ . Remove (DNM);

(45)   }

(46) }

In line number 26, the function $s_p$ . $StartTracking\left(\hspace{0.17em}\right)$ instructs the proxy node $s_p$ to start reporting process of the sensed data. All sensed data of the objects $M=\left\{o_{\mathrm{1}},o_{\mathrm{2}},o_{\mathrm{3}},\dots ,o_x\right\}$ are saved in the $SOT\left(s_p\right)=\left\{{r_{\mathrm{0}},r}_{\mathrm{1}},r_{\mathrm{2}},\dots ,r_x\right\}$ where $r_i\hspace{0.17em}\hspace{0.17em}\left(i\le x\right)$ is a record reference for the object $o_i$ and each $r_i=\left\{m_{\mathrm{0}},m_{\mathrm{0}},m_{\mathrm{0}},\dots ,m_x\right\}$ where $m_i\hspace{0.17em}\hspace{0.17em}(i\le x)$ is the current sensed data (see Figure 5(a)). The proxy node $s_p$ reports the records in $SOT\left(s_p\right)$ sequentially. The records in $SOT\left(s_p\right)$ 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 of k 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 ( $E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}$ ) is $\mathrm{50}$  nJ/bit. $E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}$ depends on the factors such as the digital coding, modulation, filtering, and spreading of the signal. The free space model of transmitter amplifier is ${\epsilon }_{\mathrm{f}\mathrm{s}}=\mathrm{10}$  pJ/bit/m² and the multipath model of transmitter amplifier is ${\epsilon }_{\mathrm{m}\mathrm{p}}=\mathrm{0.0013}$  pJ/bit/m⁴. 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 $t_{\mathrm{0}}=\sqrt{{\epsilon }_{\mathrm{f}\mathrm{s}}/{\epsilon }_{\mathrm{m}\mathrm{p}}}$ (meters), the free space ( $\mathrm{f}\mathrm{s}$ ) model is used; otherwise, the multipath ( $\mathrm{m}\mathrm{p}$ ) model is used, as shown in (13). A sensor node will consume $E_{Tx}\left(d,k\right)$ of energy to transmit k bits size message over distance d and consume $E_{Rx}\left(d,k\right)$ of energy to receive transmit k bits size message:

$$\begin{array}{cc}& E_{Tx}\left(d,k\right)=\left\{\begin{array}{cc}\left(k·E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}\right)+\left(k·{\epsilon }_{\mathrm{f}\mathrm{s}}·d^{\mathrm{2}}\right),\hfill & d<t_{\mathrm{0}},\hfill \\ \left(k·E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}\right)+\left(k·{\epsilon }_{\mathrm{m}\mathrm{p}}·d^{\mathrm{4}}\right),\hfill & d\ge t_{\mathrm{0}},\hfill \end{array}\right.\\ E_{Rx}\left(k\right)=k·E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}.\end{array}$$

(13)

For performance evaluation, we developed a software using c# (Visual Studio 2012). We will use three different coverage schemes as shown in Figure 7.

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.

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)

Table 3 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_{\text{elec}}$$	50 nJ/bit
$${\epsilon }_{\text{amp}}$$	0.001 pJ/bit/m2
BS location	Inside
Network topology	Grid coverage 1

The evaluation results for using GHS on grid coverage version (1) are shown in Figures 8 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 ( $E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}$ ). In each round, each sensor sends a packet of 1024 bits. The green progress bar indicates the residual energy.

In 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) is 4.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)

Table 4 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_{\text{elec}}$$	50 nJ/bit
$${\epsilon }_{\text{amp}}$$	0.001 pJ/bit/m2
BS location	Inside
Network topology	Grid coverage 2

In Figure 10, 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 ( $E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}$ ). In each round, each sensor sends a packet of 1024 bits. The green progress bar indicates the residual energy.

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_{\text{elec}}$$	50 nJ/bit
$${\epsilon }_{\text{amp}}$$	0.001 pJ/bit/m2
BS location	Inside
Network topology	Zigzag

In Figure 12, 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 ( $E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}$ ). In each round, each sensor sends a packet of 1024 bits. The green progress bar indicates the residual energy.

Figure 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 ( $E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}$ ) is 50 nJ/bit. The green progress bar indicates the residual energy.

8. Conclusion and Further Works

This paper intended to develop a Sensors Grouping Hierarchy Structure (GHS) for partitioning the nodes into groups according to the maximum 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. This structure 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.