A Self-organizing Concurrent Global Information
Dissemination Scheme for Sensor Networks
Ehssan Sakhaee, Naoki Wakamiya, Masayuki Murata
Graduate School of Information Science and Technology
Osaka University
Osaka, Japan{sakhaee, wakamiya, murata}@ist.osaka-u.ac.jp

Abstract—In this paper we propose a distributed and selforganizing scheme for establishing efficient energy-saving
concurrent data dissemination for wireless sensor networks. The
proposed protocol is aimed at applications where all sensor nodes
need to provide their current data concurrently and periodicallyback to the sink, whist having an option to provide instantaneous
individual node data upon sensing. Hence, the scheme provides a
hybrid time-driven and an event-driven mechanism. The scheme
initially establishes the hopcount of sensor nodes from the sink
and identifies the highest hopcount nodes (HHN) of the sensor
network. An application scenario is the periodical recovery of the
global extremity value back to the sink by only using the HHNs
for initiating the broadcast, which inherently traverses all sensor
nodes due to the nature and position of such nodes. Thisapproach can hence effectively retrieve sensor data from allnodes concurrently in its target application. Furthermore, thescheme provides a platform for other data-centric protocols toefficiently and concurrently disseminate data from all nodes in
the network.
Keywords—self-organization; energy-efficient data
dissemination; sensor network routing.

I.
INTRODUCTION
Information dissemination and reporting is an integral
function of sensor networks. Due to the primary limitation of asensor network, namely its lack of energy, it is important todesign protocols that can effectively report data back to thesink without overtly exhausting the energy of the nodes. In
this paper we propose a routing protocol for sensor networks
which, upon establishing the current hopcount of all nodes
from the sink, identifies the highest hopcount nodes (HHNs)of the network in a self-organizing manner. The HHNs are
special (source) nodes from which their broadcast is able toefficiently reach all nodes within the network. Once the HHNs
identify themselves, they will periodically broadcast an
information packet which is updated and forwarded byintermediate nodes back to the sink. This efficient mechanism
can save a considerable amount of energy by eliminating theneed for individual node broadcasts and flooding of the
network, whilst presenting concurrent sensor data or somedata which relies on all sensor data (such as max/min/average)
back to the sink. This is especially important for nodes closer
to the sink as in traditional sensor network routing protocols,such nodes tend to lose the most amount of energy, due totheir extensive forwarding (relaying) of messages from othernodes in the network (positioned further away from the sink)to the sink [11]. The primary application of this scheme is forsensor networks where simultaneous or concurrent data fromall sensor nodes are required to determine a value, orparameter. A direct example of this is a sensor network, where
the sensors report the current extreme value (e.g. highest
temperature/pressure) of a field periodically back to the sink.
The proposed routing mechanism which is initiated by the
HHNs is dubbed as the highest hopcount node-initiated(HHNI) routing. Additionally an event-driven mechanism is
integrated into the distributed and self-organizing HHNI
algorithm, dubbed Sensor Node Initiated (SNI) routing, whichallows individual sensors to be triggered when a threshold isreached, and report their current values to the sink prior to theperiodic reporting of HHNI algorithm.
Why is the approach self-organizing? In self-organizing
systems such as those in biological and emergent systems, allindividual organisms follow identical set of rules, however
behave and react differently depending on feedback from their
immediate environment (local information) [3]. However, anemergent property or favorable global property emerges fromsuch simple local interactions. Similarly, in the proposed
protocol, each node follows the same set of rules, andestablishes its status (e.g. HHN/normal node, and hopcount tosink) based on the feedback from its own neighbors (locally)
without any global knowledge. The emergent properly of theresulting network is efficient concurrent dissemination of fielddata back to the sink. We believe that self-organization isimportant in sensor networks in order to provide 1) costeffectiveness and quick setup of an efficient network without
predefining node states, 2) reduction or elimination ofcentralized control, and 3) freedom from tinkering individual
node behavior pre/post-deployment.
The proposed scheme may be used in conjunction withother routing protocols to more efficiently report any form ofdata back to the sink. Hence it is believed that the scheme canalso be adapted to and or adopt other data aggregation
techniques used in some data-centric protocols. However inthis paper the application scenario is based on extreme value(maxima/minima) reporting of data to demonstrate the basic
mechanism of the protocol and its effectiveness in its target
application.

II. BACKGROUND
In [1] a scalable and energy-efficient routing scheme is
proposed for large-scale wireless sensor networks. This
protocol, however requires the knowledge of location of nodes
throughout the network. Other such well-known protocols
include the Greedy Perimeter Stateless Routing (GPSR) [2]and its extensions [4] used for sensor networks, which also
requires the knowledge of position of nodes for making
routing decisions. However, in many cases, knowledge ofsensor locations is costly and often infeasible for wirelesssensor networks. Previous energy-efficient routing schemes do
not tackle the fundamental issue of redundant broadcasting.
Probabilistic forwarding is proposed [5] [6] which reduce theenergy consumption of nodes by eliminating flooding.
However, the scheme does not immune the network against
redundant (initial) broadcasts by individual nodes, whichwastes precious node energies, often, unnecessarily. Some ofthe protocols also require flooding of the network to obtaincosts of paths, which is another energy-depleting mechanism
used in traditional networks. Geographic and Energy Aware
Routing (GEAR) [7] also tries to minimize energy usage byusing geographic location of nodes. However, this also
requires the position of nodes.
With regards to data-centric protocols, Sensor Protocol for
Information via Negotiation (SPIN) [8] was one of the firstattempts to reduce redundant and duplicate data fromcirculating. However the advertisement in SPIN will again use
more energy than is required for the target application ofobtaining extreme value of a field, although SPIN may be
more suitable for more sophisticated data aggregation
applications. Another issue with SPIN is that intermediate
nodes which are not interested in the data may prevent thedata to be delivered to a sink which is far away from source[9]. Directed Diffusion [10] is yet another data-centric
protocol which aims at diffusing interest data throughattribute-value pairs for the required data. The protocol
requires querying nodes for interest data, which may incur
additional and unnecessary energy consumption when applied
to the application target of extreme-value discovery of a
network, or where the data to be obtained requires or is afunction of all sensor nodes within the network. Furthermore,hierarchical data aggregation techniques have been proposedsuch as LEECH [12] and HEED [13], which aggregate nodedata at specific nodes called clusterheads. However, thecluster-based approaches are again not suitable for theapplication of extreme-value discovery of a network. Other
generic data aggregation techniques are outlined in [14].
III.

Fig 1. Network topology.

redundant rebroadcasts are minimized by selectiveforwarding, which involves performing simple comparisons ofconsecutive messages at each node, via locally saved
information and only forwarding “selected” messages.
Moreover, a random waiting mechanism is integrated at eachnode for avoiding identical message broadcasts/rebroadcasts
which further minimizes redundant rebroadcasts. In the initialmodel, it is assumed all nodes are equally spaced from eachother. We also assume the sink functions separately to the restof the sensor nodes in the network; however it uses the sametransmission range as the other nodes within the network. In
Fig. 1, the transmission range of nodes is set to one-hop. The
black node (0.0) represents the sink, the grey nodes represent
sensor nodes where nodes with hopcounts less than 9
represent the intermediate (ordinary sensing/forwarding)nodes and the node with hopcount equal to 9 representing the
HHN node.
In order for nodes to discover their relative hopcount to thesink and for HHNs to establish their HHN status dynamically,
we use the following initialization algorithm.
1.

Sink broadcasts an “S” message to neighbors.

2.

Neighbors of sink update their hopcount to sink to 1
and broadcast a “1” hopcount message to their own
neighbors.

3.

An intermediate node whose hopcount is yet
undefined, sets its hopcount value as the minimum
among all received hopcount messages plus 1, andbroadcasts this hopcount to its neighbors.

4.

Nodes set their kmax variable, which is the number ofneighbor nodes with the same hopcount. Thisvariable is set after overhearing neighbors
broadcasting their hopcount messages.

5.

When a node does not receive a hopcount message
with a larger hopcount than its own, it assumes it is
the HHN of the field.

THE PROPOSED SCHEME

A. Highest Hopcount Node-Initiated (HHNI) Routing
The main aim of the proposed protocol is to minimize
redundant broadcasts by broadcast initiation of certain nodes
that allow subsequent traversal of all nodes in the network in
an efficient way, instead of individual nodes broadcasting
their values. Such nodes are termed the highest hopcountnodes HHNs which initiate broadcast and other intermediate
nodes simply update the message and forward it on towards
the sink. This idea is illustrated in Fig. 1. Additionally,hopcount message with a larger hopcount than itself, does not
update its hopcount, because it sets its hopcount value as theminimum plus 1. Hence it also does not rebroadcast ahopcount message upon receiving one with a larger hopcountthan itself.
After the initialization is complete, all nodes will know
their hopcount to sink and HHNs have identified themselves.
The hopcount message also contains the periodic time interval
for which broadcast should be initiated. Once the HHN nodes
are identified, they would proceed with periodic broadcasts of
information regarding their environment (e.g. temperature,pressure etc). Upon the initiation of the broadcast of the HHN,
the nodes which have a lower hopcount than their parent node(the node that the broadcast is heard from) will continue
forwarding the broadcasted messages until it reaches the sink.
This is the basic principle of HHNI routing. In addition to thismechanism, we can further reduce redundant rebroadcasts byaggregating data or depending on the application storing theextreme (e.g. maximum/minimum) known and discovered
values at each forwarding node, and having such a node checkconsecutive messages (identical timestamps) and only forward
the ones that have higher extreme values than those stored at
the node. We classify this as selective-forwarding of HHNI or
HHNI-SF. At this point other data aggregation andcomparison techniques may also be incorporated.

Fig. 2. Unified HHNI/SNI algorithm.

The hopcount initialization is propagated from the sink tothe edge of the network and this leads to the minimum
initialization overhead by making each node broadcasts a
hopcount message only once. A node, which receives a

Reporting in the proposed scheme can occur via twomeans: HHNI broadcasting, and Sensing Node Initiated (SNI)
reporting (also an inherent broadcast). The SNI uses its own
message type which bypasses the comparison algorithm of the
HHNI scheme. The SNI simply needs to report the specificvalue of a sensing node to the sink, and is not interested in thevalues of other nodes in the field. The unified algorithm isshown in Fig. 2. In the figure, n is the current node, p is theimmediate parent of the current node (from which the message
was received), t is the current time (initialized to zero), tn is
the interval between each periodic broadcast, tw being thewaiting time before broadcast forwarding (priority waiting), tra random time between zero and tmax, where tmax is the
maximum random waiting time allowed, and δt an incremental
period. k is an integer variable which is incremented each timea node broadcasts, and decremented each time a node
overhears a broadcast. h is the number of overheard (HHNI)
broadcasts, and is incremented by one each time an identicaltimestamp HHNI broadcast of the same hopcount as n isheard. If h does not reach kmax, it indicates that one or moreneighbor nodes have not responded, implying a failed
neighbor node, and so a Failed Neighbor message is sent tothe sink indicating the ID of the failed node (FNID) which did
not respond. The value of kmax is determined for each node
during the initialization phase described earlier. This isdirectly proportional to the number of neighbors present whichhave the same hopcount as n. Value corresponds to the data
value, which is assumed a single value in this case. The cacheis the local memory of the node where values andcorresponding identifiers and timestamps of received
messages are stored.
We note that when an intermediate node receives a SNI
message type, it will wait for a random time before
broadcasting to see if its neighbors broadcast the same

message. Each time a message is broadcasted by a node, therandom waiting time is incremented by δt and decremented bythis value when a node overhears a broadcast by its neighbor.
This is to first give priority to nodes which have notpreviously broadcasted, and then conceive priority onceneighbors have broadcasted. This prevents nodes of the same
hopcount that hear the message from broadcasting the samemessage avoiding redundant broadcasting whilst providing amore distributed broadcasting mechanism to reduce individual
node energy exhaustion.
This random time waiting
mechanism is only used for SNI reporting, as in HHNI,
information from all nodes is required. In the target
application network, the number of sources is equivalent to thenumber of nodes in the network (excluding the sink).
The sink is also able to set the current network’s extreme
value (X-Value) and threshold of all nodes, which is used by
the node to monitor its current value for SNI reporting. If anode receives a sink extreme value broadcast (SXVB)
message, it will set the X-Value and Threshold. Once thesetwo values are defined at a node, the node compares its sensed
data (value) against these values. This usually happens uponchanges in the sensed data’s value. The X-Value simply
determines whether the SNI reporting occurs when the node’s
currently sensed data falls above or below the threshold. For
instance, if we wish a node to report its value when its current
value falls below the threshold, we set the threshold below the
X-Value, otherwise we set the threshold above the X-Value if
we wish to have the node report its value when its current
sensed value rises above the threshold. Finally, the sinkcollects and evaluates the messages, obtaining/extracting thedesired value or extremity and broadcasting this to all sensor
nodes (for HHNI) or simply using the value obtained without
further input into the system (SNI).
Pure HHNI reporting simply forwards the message on
without comparing values. However, this acts as a clear
platform for other potential data-centric, aggregation, andnegotiation protocols which are in existence [9] [14] to be able
to effectively and efficiently retrieve values from all nodes
concurrently. Pure HHNI is used when the values of all nodes
are to be collected and studies, e.g. for scenarios where theaverage of all sensor nodes’ values need to be obtained, or
where statistical evaluation of sensor values needs to bestudied. However, it should be noted that in the target
application in this paper, we are not considering data
negotiation in our protocol as used in some of the previous
data-centric protocols such as [8] [10] as we assume there isno overlap [8] in the sensing regions. Hence each nodeuniquely obtains the value of its own unique region. Despite
this assumption, the proposed protocol may be adaptable todata negotiation schemes for the application of disseminating
all sensor node data concurrently and efficiently.
B. Message Types
The message types are shown below. The Type field
specifies whether the message is of type HHNI or SNI, sincenodes will react differently depending on the type of message.
The HHN ID, (HHNID) is the unique ID of the HHN initiating
the broadcast. This ID can be set statistically (predefined), or
can be generated dynamically, however it must be unique. For

instance the ID can be a function of the hopcount to sink andthe node’s residual energy at the time of instantiation. For the
HHNI broadcast, the Value field corresponds to the maximum
value so far, whereas in the SNI message, the value
corresponds to the value at the specific node with ID of SNID
(hence this field is not updated) as the message is propagated.
In the SXVB message, the X-Value is the extreme value of the
network at the instance of data collection at the sink, extracted
from the HHNI or SNI broadcast/reporting. The Thresholdfield is used to monitor the value of the current node. If thethreshold value falls below or above this value, then a SNIreport is triggered to immediately report the current node
value to the sink. The X-Value is used at each node to
determine whether triggering occurs when the value of node
falls below or above the threshold.
HHNI broadcast< Type: HHNI><HHNID><Value><Hopcount><Timestamp>
SNI reporting< Type: SNI><SNID><Value><Hopcount><Timestamp>
SXVB broadcast<Type: SXVB><X-Value><Threshold>Note that the Hopcount field is updated with the current
node’s hopcount at each node before the message is forwardedon (provided it is forwarded). A node can distinguish between
a HHNI, SNI, and SXVB broadcast by simply checking theType field of the message.
C. In case of Node Failure
Failure of HHNs: When a node which was previously aneighbor of a HHN does not hear a HHN broadcast for someperiod tm where tm is given by tm = mtn and where m is thenumber of missed broadcast intervals and tn is the interval
between broadcasts, it will claim the status of a HHN and
begin its function as a HHN (i.e. performing periodic
broadcasts). This follows the self-organizing rule.
Failure of non-HHN Nodes: Failed nodes can be physicallyreplaced by new nodes if necessary, in which case the newnodes can update their hopcount-to-sink as they overhear or
forward the messages initiated by the HHN. This is also
effective when relative node positions of normal nodes
change, in addition to the new deployment of new nodes in the
network.
Moreover, in addition to the self-organizing rules
mentioned, a “backup” centralized mechanism may be used,
where when a periodic broadcast is not heard at the sink
(failure of HHNs), a new H/HHI procedure can take place.
However this is not necessary and acts as a backup to the selforganizing procedure. Hence the network can function purely
without any feedback from the sink, provided the H/HHI
occurs just once in order to initialize the network.

7

broadcast frequency

ave. broadcast frequency

3

2

1

6
5
4
3
2
1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17

199

188

177

166

155

144

133

122

111

89

100

78

67

56

45

34

23

1

1

12

0

0

hopcount to sinkhopcount to sink
Fig. 4. Average broadcast frequency of individual nodes for 10,000 nodes.
Fig. 3. Broadcast frequency of individual nodes for 100 nodes.

total no. of broadcasts (inthousands)

10

100 nodes
900 nodes
1600 nodes
2500 nodes

9
8
7
6
5
4
3
2
1
0
60

180

300
range

420

540

Fig. 5. total number of broadcasts with varying transmission range.

IV. SIMULATIONS
Simulations were performed to evaluate the effectivenessof the proposed scheme. The application platform is forreporting the highest value sensor node back to the sink. Nodevalues are randomly chosen, between zero and one. Each nodecontains a random value. The distance between nodes is set toa fixed 50 units. A rectangular topology is used similar to theone shown in Fig.1. In all simulations the HHNs are theinitiator for broadcasting. Furthermore the highest value nodeis reported back to the sink (simulating HHNI-SF algorithm).
Fig. 3 and Fig. 4 show the frequency of broadcast (number oftimes a node performs a broadcast, including initial broadcast,and forwarding) by individual nodes for a field of 100 nodes
and 10,000 nodes respectively, for the first round of reporting
initiated by the HHN (node with hopcount of 199).
In Fig. 3, the transmission range is set to 60 units(equivalent to one-hop), so that nodes only broadcast to their
one-hop neighbors. Fig. 5 shows the total number ofbroadcasts when varying the transmission range for different
network sizes (characterized by the number of nodes). The
effect of increasing the transmission range here has the same
effect as increasing the node density, e.g. by reducing the
distance between sensor nodes, so that the sensor node canFig. 6. Formation of HHNs with increasing transmission range.

reach more than one-hop neighbors. From Fig. 3, it can beseen that the maximum average broadcast frequency of 2.5
belongs to nodes one-hop away from the sink. As node
hopcount from sink increases, the number of broadcasts tends
to decrease. Similarly in Fig. 4, the same trend is observed,
although the average broadcast frequency is higher for the
network with 10,000 nodes. Although the general trend is adecrease in broadcast frequency with increasing hopcount, theactual frequency also depends on the relative location of
extreme value nodes, which causes the downstream nodes toperform additional broadcasts. In Fig. 5, as we increase thetransmission range of sensor nodes, the total number ofbroadcasts increase. The best performance is achieved when
the transmission range is equivalent or close to a one-hoptransmission. This is the case regardless of the network size. It
is interesting to note that as the transmission range increases,
so do the number of HHNs. This is shown in Fig. 6 for thecase where the transmission range is increased to two-hops.
This is due to the nature of the algorithm, which impels nodes
that do not overhear a broadcast greater than their own
hopcount, to elect themselves as HHNs. The result of this isthe increase in the number of broadcasts as visible in Fig. 5. In
the figure, there are a total of 16 HHNs. We note that although
the highest hopcount in the field is six hops, some nodes
which have a hopcount of 5 have elected themselves as HHN.
Although these nodes do not possess the highest hopcountglobally, they are locally the highest hopcount nodes as theactual HHNs (hopcount of 6) are not within their range. We
note that the local HHNs are necessary for traversing all nodes
within the network.

V. CONCLUSION AND FUTURE WORKIn this paper we propose a scheme for efficiently reporting
extreme values of a field-based sensor network, by first
identifying the highest hopcount nodes of the network, which
their broadcasts are capable of penetrating all nodes within the
network efficiently. Consequently this approach is able toreport extreme values of the network to the sink as efficiently
as possible. The principle idea may also be integrated into
future protocols depending on the application. For example,
cost-based sensor network routing protocols may effectively
use the highest-hopcount-node-initiated (HHNI) broadcasting
scheme presented in this paper to more efficiently performrouting in sensor networks based on various metrics such asenergy, delay, and hopcount.
In future work, the effect of mobility of nodes should beconsidered to support more dynamic and mobile networks.
Furthermore, since in this paper it is assumed that the links arebidirectional, the effects of unidirectional links can also be
considered in future research. Although the simulated
application scenario involves a uniformly distributed topology,
random layout networks may also take advantage of the
proposed scheme. However the limitations (if any) of the
proposed scheme on randomly distributed sensor networks
should be investigated in further detail.

ACKNOWLEDGEMENTS
This research was supported in part by the “Global COE(Centers of Excellence) Program” of the Ministry of
Education, Culture, Sports, Science and Technology, Japan.

REFERENCES[1]

G. Lukachan, M. Labrador and W. Moreno, “Scalable and energyefficient routing for large-scale wireless sensor networks,” in Proc.
ICCDCS’06, Mexico, Apr. 2006.
[2] B. Karp, and H. Kung, “Greedy perimeter stateless routing,” in Proc. 6th
ACM MobiCom’00, Boston, MA, Aug. 2000.
[3] S. Kauffman, “At home in the universe: the search for the laws of selforganization and complexity,” AIP Press, 1995.
[4] J., Chen, Y., Guan, U. Pooch, "Customizing a geographical routing
protocol for wireless sensor networks," in Proc. ITCC’05, vol.2, no., pp.
586-591 Vol. 2, 4-6 Apr. 2005.
[5] K. Chen, Y. Qin, F. Jiang, Z. Tang, “A probabilistic energy-efficientrouting (PEER) scheme for ad-hoc sensor networks,” in Proc.
SECON’06, vol. 3, pp. 964-970, Sept. 2006.
[6] R. C. Shah, and J. Rabaey, “Energy aware routing for low energy ad hoc
sensor networks,” in Proc. IEEE WCNC’02, Orlando, FL, Mar. 2002.
[7] Y. Yu, D. strin, and R. Govindan, “Georgraphical and energy-awarerouting: a recursive data dissemination protocol for wireless sensor
networks,” UCLA Com. Sci. Dept. tech. rep., UCLA-CSD TR-010023,
May 2001.
[8] W. Heinzelman, J. Kulik, and H. Balakrishnan, “Adaptive protocols for
information dissemination in wireless sensor networks,” in Proc. ACM
MobiCom’99, Seattle, WA, Aug. 1999.
[9] J. N. Al-Karaki, A. E. Kamal, “Routing techniques in wireless sensor
networks: A survery,” Wireless Communications Magazine, Dec. 2004.
[10] C. Intanagonwiwat, R. Govindan and D. Estrin, “Directed diffusion: A
scalable and robust communication paradigm for sensor network,” inProc. 6th ACM MobiCom’00, Boston, MA, Aug. 2000.
[11] P. Cheng, C. N. Chuah, X. Liu, “Energy-aware node placement inwireless sensor networks,” in Proc. IEEE GLOBECOM’04, vol. 5, pp.
3210-3214, Dec. 2004.
[12] W. R. Heinzelman, “Application-specific protocol architectures for
wireless networks,” Ph.D. thesis, Massachusetts Institute of Technology,
Jun. 2000.
[13] O. Younis and S. Fahmy, “HEED: a hybrid, energy-efficient distributed
clustering approach for ad hoc sensor networks,” IEEE Trans. Mobile
Computing, vol. 3, no. 4, pp. 366-379, Dec. 2004.
[14] R. Rajagopalan, P. K. Varshney, “Data-aggregation techniques in sensor
networks: a survey,” IEEE Communication Surveys and Tutorials, vol. 8,
pp. 48-63. 4th Quarter, 2006.