GROUP: a Grid-clustering Routing Protocol for Wireless Sensor

Networks∗

Liyang Yu, Neng Wang, Wei Zhang Chunlei Zheng

Dept. of Computer Science & Technology Shanghai Institute of
East China Normal University Microsystem and Informantion Technology
Shanghai, 200062, China Shanghai, 200050, China
{lyyu, nwang, wzhang}@cs.ecnu.edu.cn [email protected]

Abstract∗ receiving data packets and control packets (e.g. the routing
message). An energy-efficient routing protocol can reduce
In this paper, we propose GROUP, a grid-clustering control packets and support in-network data processing
routing protocol that provides scalable and efficient packet which can reduce data packets greatly and only transmit
routing for large-scale wireless sensor networks. The sink processed and necessary data instead of all raw data to the
proactively, dynamically and randomly builds a cluster grid sink. A lot of routing protocols [3][4][7][9] for wireless
structure in GROUP. Only small part of all sensor nods will sensor networks have been proposed by researchers in past
participate in election of cluster heads. GROUP can few years. Due to wireless sensor networking is an
distribute the energy load among the sensors in the network, application-specific technology; the existent routing
and provide in-network processing support to reduce the protocols for wireless sensor networks can not meet the
amount of information that must be transmitted to the sink. requirements of all applications of WSNs. We are attempting
We have evaluated the performance of GROUP through to design an energy-efficient routing protocol for the
simulation experiments. The results of simulations show that application scenario like as real-time forest fire detection [10].
GROUP is an energy-efficient and scalable routing protocol In this paper, we focus on the design of GROUP which is
for large-scale wireless sensor networks. an energy-efficient and cluster-based routing protocol for
wireless sensor networks. In GROUP, one of sinks
Keywords: wireless sensor networks, routing protocol, grid- proactively, dynamically and randomly builds a cluster grid
clustering to forward query messages and data packets. In order to
detect the forest fire, a large number of sensor nodes, which
can measure environment temperature, relative humidity and
1. Introduction
smoke, are densely deployed in the forest. With GROUP,
these nodes can be dynamically organized into clusters so
The wireless sensor network (WSN), which has a variety
that each node has a corresponding cluster head at certain
of potential applications, is an attractive research area in the
time. Sensor nodes also can receive query messages from
past few years. Such a network usually consists of a large
sinks and forward data packets to sinks through GROUP.
number of inexpensive, tiny, and low power sensor nodes
We choose grid structure for cluster heads based on
that organize themselves into a multi-hop wireless network.
following two considerations. First, grid structure can
These sensor nodes typically are left unattended (e.g. in
guarantee good cluster head distribution. Second, the routing
hostile environments) and powered by batteries. It is difficult
between cluster heads is simple in grid structure. And cluster
and impossible to recharge or replace their batteries.
heads can select one route from multiple candidate routes to
Energy efficiency is one of core challenges in wireless
forward data packet to sinks based on residual energy and
sensor networks because energy is scarce and valuable. In
load balance.
order to minimize energy expenditure and maximize network
The remainder of this paper is organized as follows.
lifetime, numerous energy-aware protocols and algorithms
Section 2 describes the design of GROUP. The simulation
for wireless sensor networks (e.g. S-MAC [8], SPIN [5])
results will be shown in Section 3. In Section 4, we discuss
have been proposed by researchers.
related issues. Finally, Section 5 concludes this paper.
The study [6] shows that energy consumption is
dominated by communications for wireless sensor networks.
And communications are dominated by sending and
2. Grid-clustering routing protocol
There are several network models for wireless sensor
∗
This work is supported in part by Shanghai Municipal Science and networks. In this work, the network model is based on the
Technology Commission under Grants No. 05dz15004 (Research following assumptions:
on key technologies of wireless sensor networks and application in
road traffic).

1-4244-0517-3/06/$20.00 (c) 2006 IEEE

 y All sensor nodes are stationary and ware of their own
locations through location techniques such as the
recursive position estimation [2]. S1
y The number of sinks may vary over time. All sinks can
communicate with each other through tethered network
or satellite. R S2
y Each sensor node is able to adjust its wireless
transceiver’s power consumption. The cluster heads GS
communication with each other through long-range
radios while other sensor nodes communication with
respective cluster head through short-range radios.
In GROUP, all sensor nodes are divided into several R
clusters dynamically. One node is selected as the cluster Figure 1. Example cluster grid
head (CH) in each cluster. And all cluster heads form a the new GS is the same as the current GS, this run of cluster
virtual cluster grid. The data queries will be transmitted from grid construction process will be terminated. Otherwise, the
sinks to all nodes via cluster heads. And the data matched the PS will ask the new GS to select more cluster heads around
query are routed back to sinks via cluster heads too. The the network.
application-specific data aggregation policy can be applied in The GS is at one crossing point of the constructing cluster
cluster heads. grid. Let GS’s location LGS = (xGS, yGS), crossing points are
We begin to describe GROUP from how to select cluster
located at Lp = (xi, yj), where x = xGS +R×i and yj = yGS+R×j
heads dynamically, i.e. the cluster grid construction process.
(i, j = 0, ±1, ±2, ±3, …). For every crossing point, GROUP
will select one sensor node, which is closer to the crossing
2.1. Cluster grid construction point than other nodes, as the cluster head.
The new GS broadcasts a CH-election packet, containing
After the wireless sensor network is deployed, all sinks in LGS and cell size R, to its neighbors to elect its four
the network will elect one sink as the primary sink (PS), who downstream cluster heads. All sensor nodes will store the
initiates the cluster grid construction process, based on their latest CH-election packet for failure recovery (discussed in
location. The PS is closer to the center of network than other section 2.4). The neighbors, who received the CH-election
sinks in order to keep a minimum duration of grid packet, calculate the distance to the four crossing points
construction. For example, in Fig. 1, sink S2 is the PS. If based on LGS and cell size R. If the distance to one of the four
sinks are mobile, the PS will vary with the sinks’ mobility. crossing points is less than 0.5R, the node will compete with
Every T seconds, PS initiates the cluster grid construction its neighbors for becoming a cluster head by broadcasting a
process by broadcasting a GS-election command within its CH-candidate packet to its near neighbors after an interval.
radio coverage range. The aim of GS-election command is to In order to reduce the number of CH-candidate packet, the
elect one sensor node as the Grid Seed (GS) from PS’s interval is in proportion to the distance to the crossing point.
neighbors. In the GS-election command, there are three So the node has smallest distance will usually send out the
important parameters, i.e. PS’s location LPS = (xPS, yPS), cell CH-candidate packet firstly. If a node who received the CH-
size R and probability p. All the sensor nodes who received candidate packet has smaller distance to the crossing point, it
the GS-election command will decide whether to answer the will broadcast a new CH-candidate packet. Otherwise, it will
PS or not based on these parameters. Let node N’s location keep silent on election of cluster head. Finally, the node who
broadcasts the last CH-candidate packet becomes a new
LN = (xN, yN), if |xPS − xN | > R/2 or |yPS − yN | > R/2 node N
cluster head.
will not answer the PS. Otherwise, node N will answer the
The new cluster head sends a CH-new packet to the GS
PS by sending a GS-reply packets to it with a probability p. and stores the GS’s information in its cache as its upstream
And we name the node N as the candidate of GS. cluster head. Then the new cluster head broadcasts a CH-
When the PS sent out the GS-election command, it started election packet to elect its downstream cluster heads like the
a timer. If the PS didn’t receive any reply from its neighbors GS does. The election of cluster head will be iterated until all
before the timer expires, it will resend the GS-election with a cluster heads are elected. And during the election, duplicate
bigger probability p. CH-election packets identified by the sequence number will
The PS will select one node as the new GS from all be simply dropped.
candidate nodes based on candidates’ residual energy. The When a node received a CH-election packet from the GS
candidate who has more residual energy than other or a cluster head, it also calculates the distance to the node
candidates becomes the new GS. If there are two or more which transmitted the CH-election packet. If the distance is
candidates who have same residual energy and have more less than 0.7R, the node will store the information of the
residual energy than other candidates, the one whose reply sender and become the member of this cluster.
packet arrived at PS earlier will be selected as the new GS. If

1-4244-0517-3/06/$20.00 (c) 2006 IEEE

 Average end-to-end delay of data
Data Forwarding
2.5 20

Energy Consumption (Joule)

Maximum
2 Average 15
Minmum

packet (ms)
1.5
S 10
N3
GS 1 1
N1 N2 GS0 5
N0 0.5
0 0
120 160 200 240 280 320 120 160 200 240 280 320
Cell Size (m) Cell Size (m)

Figure 2. Data forwarding during Figure 3. Energy consumption with Figure 4. Average end-to-end delay of
cluster grid construction different cell sizes data packet with different cell sizes
2.2. Query forwarding 2.4. Failure recovery
In the application scenario of forest fire detection, there In wireless sensor networks, the sensor node is prone to
are two typical classes of queries sent by sinks, i.e. location- failure. It is important and necessary to handle unexpected
unaware query and location-aware query. In GROUP, they component failures for robustness. Only the failure of cluster
are forwarded through limited-broadcast and unicast head will impact the query forwarding and data forwarding
respectively. in GROUP.
The location-unaware query, e.g. which area(s) has When a cluster head failed, the sensor node, which tries to
temperature higher than 40°C, is transmitted from one of the transmit query or data to it, broadcasts a CH-search packet to
sink to its closest cluster head firstly. The cluster head then elect a new cluster head to replace the failed cluster head.
broadcasts the query through long-range radio. While its four The neighbors of failed cluster head will elect a new cluster
neighbor cluster heads will re-broadcast the query, the head based on the CH-search packet and latest CH-election
member node will not re-broadcast the query. packet like the election of cluster head during cluster grid
The location-aware query, e.g. what is highest construction. Then the new cluster head finds out its
temperature in area (0, 0, 200, 150), will be forwarded via upstream cluster head and downstream cluster head(s) by
the cluster heads by unicast. When a cluster head receives a broadcasting a CH-recovery packet.
location-aware query, it will forward the query to one of its
downstream cluster heads which is closest to the destination 3. Performance evaluation
area mentioned in the query. And only the cluster head, who
locates in the area, will broadcast the location-aware query to We implemented GROUP in ns-2.27[10] and the
its member through short-range radio. underlying MAC is 802.11 DCF. In this section, we first
evaluate how the control parameters affect the performance
2.3. Data forwarding of GROUP. Then we compare GROUP with LEACH. We
choose three metrics to analyze the performance of GROUP
Once a sensor node receives the query from its cluster to compare other scheme:
y Energy consumption is defined as the communication
head, it will check the query and collected data. If the
(transmitting and receiving) energy the network
collected data match the query, it sends out data to its cluster
consumes; the idle energy is not counted.
head through short-range radio. The data packet will be y Packet delivery fraction is the ratio of the data packets
forwarded recursively by the cluster head to its upstream delivered to the sinks to those generated by the sources.
cluster head till it reaches the sink which generated the query. y Average end-to-end delay of data packet includes all
In GROUP, cluster heads can perform data aggregation possible delays caused by queuing at the interface
expediently in order to reduce the number of data packets queue, retransmission delays at the MAC, and
and save energy. propagation and transfer times.
Fig. 2 illustrates the data forwarding during cluster grid Each simulation run lasts 200 seconds, and each result is
construction. The network is transferring to a new cluster averaged over three random network topologies. Every 2
grid whose grid seed is GS1. When the data packet from node seconds, 20 nodes are selected randomly to send the sink a
N0 reaches node N2 via node N1 according to the previous 64-byte data packet. Sensor nodes adjust their wireless
cluster grid, node N2 will transmit it to node N3 instead of transceiver’s energy consumption according to the cell size.
node GS0. Because node N3 informed its neighbor that it
became a cluster head of the new cluster grid during the 3.1. Impact of parameters on GROUP
cluster grid construction. Then the data packet will
transmitted to sink S via GS1. So cluster grid construction To evaluate the impact of control parameters (i.e. cell size
doesn’t impact the data forwarding. and interval of cluster grid construction) on GROUP, one
sink and 300 sensor nodes are randomly distributed in a

1-4244-0517-3/06/$20.00 (c) 2006 IEEE

 Average end-to-end delay of data
2 14 1
Energy Consumption (Joule)

Packet delivery fraction(%)

1.5 13.5 0.8

packet (ms)
Maximum 13 0.6
1 Average
Minmum 12.5 0.4
0.5
12 0.2

0 11.5 0
5 10 20 30 40 50 5 10 20 30 40 50 5 10 20 30 40 50
Interval of cluster grid construction (s) Interval of cluster grid construction (s) Interv al of cluster grid construction (s)

Figure 5. Energy consumption with Figure 6. Average end-to-end delay Figure 7. Packet delivery fraction
different intervals of grid construction of data packet with different intervals with different intervals
1200×1000m2 field. The sink locates at the center of the y 108 sensor nodes in a 720×600m2 field
field. y 147 sensor nodes in a 840×700m2 field
Firstly, we study the impact of cell size on GROUP’s y 192 sensor nodes in a 960×800m2 field
performance. The cell size varies from 120m, 160m, 200m, y 243 sensor nodes in a 1080×900m2 field
240m, 280m to 320m. The interval of cluster grid y 300 sensor nodes in a 1200×1000m2 field.
construction is set to 10s. Fig. 3 shows the average, All scenarios have the same distributing density of sensor
maximum and minimum energy consumption with different nodes. And all scenarios have one sink that locates at the
cell sizes. And Fig. 4 plots the average end-to-end delay of center of the field.
data packet. We make two observations. First, the energy In GROUP, cell size is set to 200m; interval of cluster
consumption increases significantly as the cell size increases grid construction is set to 20s. In LEACH, the ratio of
because larger cell size means cluster head consume more number of clusters to number of nodes is set to 5%; interval
power for communications. Second, the data packet delay of cluster head selection round is same as GROUP, i.e. 20s.
tends to decrease when there are larger cell size, because There is no aggregation operation applied both in GROUP
larger cell size means less average hops from sensor nodes to and in LEACH because the focus of this paper is not to study
the sink. Therefore, cell size should balance the energy the performance of aggregation.
consumption and the end-to-end delay of data packet. Firstly, we look at packet delivery fraction, shown in Fig.
We also evaluate the impact of interval of cluster grid 8. GROUP has clearly better packet delivery fraction than
construction. We vary the interval from 5s, 10s, 20s, 30s, LEACH, especially in the scenarios with more sensor nodes.
40s, to 50s, while the cell size is set to 200m. Fig. 5 shows We find lots of collision reports in simulation log files of
that the average energy consumption decreases slightly when LEACH. More collisions are reported in bigger scenario
the interval of grid construction increases. It implies that field. In LEACH, all cluster head forward the data packet
cluster grid construction is energy-efficient. In 40-second from cluster members to the sink directly. In bigger scenario
interval and 50-second interval cases, the maximum energy field, longer radio, which leads more collision, is used to
consumption is much more than other case’s maximum transmit the data from cluster heads to the sink in LEACH.
energy consumption because longer interval requires the But in GROUP, the cluster head will forward the data packet
cluster heads are on duty longer and forward more data to the upstream cluster head that is closer to the sink, and the
packets. Therefore, long interval should not be chosen in radio range only varies with cell size.
GROUP. When the interval increases, average end-to-end Secondly, we evaluate the energy consumption. Fig. 9
delay of data packet decreases (Fig. 6). This is due to the shows the maximum energy consumption and average
data packet usually will pass through one more cluster head energy consumption of all sensor nodes in GROUP and
during grid construction (Section 2.3). So the less grid LEACH. The maximum energy consumption is an important
construction means the less average end-to-end delay of data metric to show when the first dead node appears. And the
packet. Fig. 7 plots the packet delivery fraction with different gap between maximum and average energy consumption can
intervals of cluster grid construction. There is no significant reflect the distribution of energy consumption of all sensor
difference on packet delivery fraction with different nodes. GROUP has lower maximum energy consumption
intervals. And it implies that the cluster grid construction than LEACH but the case with 75 sensor nodes. For more
doesn’t impact the packet delivery fraction. sensor nodes, LEACH has much more maximum energy
consumption than GROUP. In all cases, GROUP has smaller
3.2. Comparison with LEACH gap between maximum and average energy consumption
than LEACH. That means GROUP has better energy
In this section, we compare GROUP with LEACH in 6 consumption distribution than LEACH. For more sensor
scenarios with different number of sensor nodes and different nodes, LEACH has worse energy consumption distribution.
size of network field: Finally, we study the average end-to-end delay of data
y 75 sensor nodes in a 600×500m2 field packet. In all cases, LEACH demonstrates significantly

1-4244-0517-3/06/$20.00 (c) 2006 IEEE

 Average end-to-end delay of data
1 7 14

Energy Consumption (Joule)

Packet delivery fraction(%)

Max w ith GROUP

6 Av g w ith GROUP 12
0.9
5 Max w ith LEACH 10

packet (ms)
0.8 Av g w ith LEACH
4 8 GROUP
0.7 3 6 LEACH
GROUP
2 4
0.6 LEACH
1 2
0.5 0 0
75 108 147 192 243 300 75 108 147 192 243 300 75 108 147 192 243 300
The number of sensor nodes The number of sensor nodes The number of sensor nodes

Figure 8. Packet delivery fraction

Figure 9. Energy consumption using Figure 10. Average end-to-end delay of
using GROUP vs. LEACH GROUP vs. LEACH data packet using GROUP vs. LEACH
lower average delay than GROUP (Fig. 10). This is due to form a virtual grid. Our simulations have confirmed that
GROUP is a multi-hop clustering routing protocol, while GROUP is an effective, scalable and energy-efficient routing
LEACH is a single-hop clustering routing protocol. And protocol for large-scale wireless sensor networks.
GROUP has lower average delay with less sensor nodes.
In summary, GROUP is a more scalable clustering 6. Acknowledgment
routing protocol than LEACH. With more sensor nodes,
GROUP has significantly better performance than LEACH. We would like to thank the anonymous reviewers for their
constructive criticisms.
4. Related works
7. References
There are many routing protocols that attempt to build
virtual hierarchy in wireless sensor networks. [1] http://www.isi.edu/nsnam/ns/, ns-2 Network Simulator.
GROUP is inspired partly by TTDD[7]. They both build [2] J. Albowitz, A. Chen, and L. Zhang, “Recursive Position
grid structure for routing in wireless sensor network. TTDD Estimation in Sensor Networks,” ICNP'01, 2001, pp. 35-41.
builds one grid structure for every source based on the source [3] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “An
while GROUP builds only one cluster grid structure based on Application-Specific Protocol Architecture for Wireless
one of sinks in whole network. And the dissemination nodes Microsensor Networks,” IEEE Transactions on Wireless
couldn’t communication with each other directly in TTDD. Communications, 2002, 1(4), pp. 660-670.
The data packet should be forwarded via other nodes from one [4] C. Intanagonwiwat, R. Govindan, and D. Estrin, “Directed
dissemination point to its upstream or downstream dissemination diffusion: A scalable and robust communication paradigm for
point. sensor networks,” in Proceedings of the ACM/IEEE
LEACH[3] is an application-specific data dissemination International Conference on Mobile Computing and
Networking, Boston, MA, USA, Aug. 2000, pp. 56–67.
protocol that use clustering to prolong the lifetime of
[5] J. Kulik, W. Heinzelman, and H. Balakrishnan, “Negotiation-
network. Its clustering terminates in a constant number of based protocols for disseminating information in wireless
iterations, but it doesn’t guarantee good cluster head sensor networks,” Wireless Networks, vol. 8, no. 2/3, pp. 169–
distribution. LEACH also proposes to use CDMA spreading 185, 2002.
codes to decrease the inter-cluster interferences. Our [6] G.J. Pottie, and W.J. Kaiser, “Wireless integrated network
simulation results also show that the performance of LEACH sensors,” Communications of the ACM, 43(5):51-58, May 2000.
is not good in large-scale wireless sensor network. [7] F. Ye, H. Luo, J. Cheng, S. Lu, and L. Zhang, “A Two-tier
HEED[9] periodically selects cluster heads according to a Data Dissemination Model for Large-scale Wireless Sensor
hybrid of their residual energy and a secondary parameter. Networks,” in ACM MOBICOM 2002, Atlanta, Sep. 2002, pp.
The clustering process terminates after several iterations in 148-159.
HEED. During each iterative process, a lot of packets are [8] W. Ye, J. Heidemann, and D. Estrin, “An Energy-Efficient
broadcasted. And HEED only address how to select cluster MAC Protocol for Wireless Sensor Networks,” in Proceedings
heads and doesn’t address how to forward packets between of IEEE INFOCOM, 2002, pp. 1567-1576.
cluster heads. [9] O. Younis and S. Fahmy, “Distributed Clustering in Ad-hoc
Sensor Networks: A Hybrid, Energy-Efficient Approach,” in
Proceedings of IEEE INFOCOM, March 2004, Vol. 1, pp. 629-
5. Conclusion 640.
[10] L. Yu, N. Wang, and X. Meng, “Real-time Forest Fire
In this paper, we described GROUP, a grid-clustering Detection with Wireless Sensor Networks,” in Proceedings of
routing protocol for wireless sensor networks. Query and IEEE International Conference on Wireless Communications,
data packet can be forwarded via the cluster heads which are Networking and Mobile Computing, Wuhan, China, Sep. 2005,
selected dynamically by one of sinks. And all cluster heads Vol. 2, pp. 1214-1217.

1-4244-0517-3/06/$20.00 (c) 2006 IEEE