Outline• Background of Wireless Sensor Networks– Benefits and challenges– Swarm intelligence– Multi-sink configuration

SelfSelf-Organized DataData-Gathering Scheme
for MultiMulti-Sink Sensor Networks
Inspired by Swarm Intelligence• Proposal of new data-gathering scheme– ACO approach to routing in a cluster– Application of ant-based clustering

Osaka University, Japan
Yuichi Kiri,Kiri, Masashi Sugano, Masayuki Murata
y-kiri@ist.osakakiri@ist.osaka-u.ac.jp• Performance evaluation through simulation experiments• Conclusion

July 10, 2007

SASO 2007

2

What is WSNChallenges WSN is Facing Now• Wireless Sensor Networks (WSN):• Lifetime– Composed of a number of sensor nodes– Sensor nodes are battery-operated– Battery recharge is impossible• Have poor memory capacity, processing power, etc.
• Communicate with neighborhood via wireless channel– Collect data over a large area

• Robustness

July 10, 2007

•Adaptability– Poor quality of wireless channels•Self-recovery capability– Sensor/Sink nodes are prone to failure

Sensor nodes*Benefits from WSN*
• Large monitoring region• Cheap laid down cost
• Comprehensive data gathering

Monitoring region

SASO 2007

Sink nodes• Scalability issues– A number of sensor nodes are deployed– Centralized control is a difficult scenario

3

July 10, 2007

Strategies for Robust WSN:

• Behavior of ants/bees as a swarm• Single-sink configuration

Swarm Intelligence

4

MultiMulti-Sink Configuration– Each agent is simple and unintelligent

Introduce single-failure point
Cause hot spot problem• Estimates only its surroundings• Interacts with neighboring agents• Obeys the local rules it has as a species

unresolved point withswarm intelligence• Due to converge-cast (many-to-one communication form)
Sensor nodes which
deplete their batteries– Their collective action creates biological order• Robust and adaptive to environmental changes• Highly scalable

Sensor nodes whichhave residual power to operate

Sink node• Multi-sink configuration

Such
Such aa self-organizedself-organized behavior
behavior isis
well
well suited
suited toto WSN
WSN
Swarm intelligence contributes to robust WSN
SASO 2007

Emerging property

SASO 2007

Strategies for Robust WSN:

July 10, 2007

Power-saving operation– Distribute load for relaying packets– Enhance robustness over sink node failure
5July 10, 2007

SASO 2007

61

Our Goal

Overview of Proposed Scheme• Divide a WSN into as many clusters as sink nodes– Sensor nodes that transmit packets to a sink node arededicated to that cluster– Adaptive clustering based on “ant-based clustering”.

Proposal of robust data gathering scheme for WSN– where multiple sink nodes are deployed– using swarm intelligence• Clusters dynamically expand or shrink• Routing is performed in each cluster• Self-organized behavior– Apply ACO (Ant Colony Optimization) approach to the routing
Determine destination via clustering• Robustness against what

Stochastically selecta next-hop node

– Very-poor-quality wireless channels– Changes in condition of the networks• Failures of sensor/sink nodes

July 10, 2007

SASO 2007

7Clusters

July 10, 2007

SASO 2007

8

Routing in a cluster:Routing in a cluster:• ACO: Behavior of ants in their foraging activity• ACO: Behavior of ants in their foraging activity

Ideas of ACO

Ideas of ACO• Find their food, selecting which path to take
– The higher pheromone value is left,
with the higher probability an ant choose to take the path
• Once the ant reaches their food, it follows the trail back to thenest, leaving some pheromone along the trail• Find their food, selecting which path to take
– The higher pheromone value is left,
with the higher probability an ant choose to take the path
• Once the ant reaches their food, it follows the trail back to thenest, leaving some pheromone along the trail– The amount of pheromone value depends on quality of path
Candidatenext-hop nodes– The amount of pheromone value depends on quality of path

Food

July 10, 2007

SASO 2007

Food

Pheromone value whichreflects quality of the path

9

July 10, 2007

SASO 2007

Routing in a cluster:Routing in a cluster:• Links which should have higher pheromone in WSN are:

• ACO approach:

Modification to ACO

Selecting NextNext-hop node

– Ones Leading to a sink node with small hop– Ones whose sensor nodes have sufficient residual power– Stochastically selects a next-hop node
• Depending on pheromone values on the links to candidate nodes• Construction of pheromone distribution:• hop-by-hop routing– Achieved by backward ants flooded from sink nodes• Backward ants leave
Flooded backward ants
pheromone on the links

Probability to choose n j as anext-hop node:nj

Pni (n j , Sni )Pheromone value a backward ant
conveys is decreased:• hop-by-hop• at a sensor nodewith little residual power
July 10, 2007

Sink nodeSending nodeni

Pni (n j , Sni )SASO 2007

1011

July 10, 2007

Pni (n j ) =nkCandidate
nodes for ni

Pni (n j , Sni )2∑ (Pn (k , Sn ) )k N∈ nii2i

Square sum of pheromone values
on the links to candidate nodes

SASO 2007122

Countermeasure against Sensor Node Failure

AntAnt-based Clustering• Failure detection is based on soft-state model• Swarm intelligence of ants

– Sensor nodes periodically transmit control packets
to exchange their pheromone– Detect failure if a node cannot receive the packets fromanother node for a predefined timeninioemerge– Clusters
through the iterations of picking up andut
tit N eggs
dropping
bs SufW•S Does
not require global informationor

Remove the failed node fromcandidate node set

nkSending node

• Ants repeatedly and stochastically pick up and drop eggs
based on the similarity with neighboring eggs

On detecting failure:njPni (n j , Sni )– Larvae or eggs are sorted by their size

Advantage of belonging a cluster,“cluster pheromone”
defined by pheromone values

Pni (n j , Sni )Candidatenodes for ni

July 10, 2007

• Exchanging Cluster pheromone• Clustering
SASO 2007

13

July 10, 2007

Simultaneouswith pheromone
exchange

SASO 2007

14Countermeasure against Sink Node Failure

Simulation Model•• Implement our scheme for the ns-2

Membership transition at the cluster level–––––

1. Detect sink node failure using soft-state model
2. Propagate this failure information through periodical
exchange as a form of cluster pheromone
3. Change their membership to other cluster
Sink node fails

Detects thesink node failure
Start transition ofcluster membership

Sink nodes
Sensor nodes

100 m

Sensing range: 10 m
Event point

Abandon theirmembership while
propagating failure
information
July 10, 2007

200 sensor nodes, randomly deployed
4 sink nodes
IEEE 802.15.4 MAC
Transmission distance: 10 m
Events: occurred at random point
every second

SASO 2007

15Sensor nodes in this circle
generate packets
to notify an event to a sink

July 10, 2007

100 m

SASO 200716

SelfSelf-Recovery from Node Failure• Effect of transmission error• 200 x pfail sensor nodes simultaneously fails at t=100 s

Event-notification rate: re/se
se: number of generated packets
regarding to the event e
re: number of received packets
by sinks regarding to the event e– Their positions are randomly distributed– Far more serious than what can actually happen in reality

10.8
0.6
0.4

0.2
About the same rateeven in the very-poor-quality
channels
00100

PER=0
PER=0.1
PER=0.2
PER=0.3
200– Have a small effect on event-notification rate
July 10, 2007

SASO 2007

300

Time [s]400500

Event-notification rate

MetricEvent-notification rate

Robustness against Transmission Error

0.8
0.6

Achieve self-recovery
capability

Sudden drop

0.4

pfail =0.05
pfail =0.10
pfail =0.15
pfail =0.20

Sensor nodes
failure0.2017Recovers within the shorttime to its previous state

10July 10, 2007

100200300

Time [s]Efficient combination:• ACO approach• Soft-state model

400500

SASO 2007

183Conclusion• Sink node located at the point of (25,25) fails at t=100– Limit the area where events occurred to a circular area with aradius 20 m at the center of the sink

• Proposed a novel data-gathering scheme for WSN withmulti-sink configuration– Self-organized behavior

Clusters converge
to 3 after sink
failureFails at t=100 [s]Event-notification rate

SelfSelf-recovery after Sink Failure

1– Inspired by swarm intelligence of ants

– Simulation results showed:• Robustness against poor-quality channels• self-recovery capability

0.8– From sensor/sink node failure

0.6

Fall steeply
to almost 0%

0.4• Future works

PER=0
PER=0.1
PER=0.2
PER=0.3

0.2
0July 10, 2007

About the samerate before thesink failure

0SASO 2007

100200300

Time [s]40050019– Examine the influences of the parameters– Clarify the differences in characteristics between selforganized and centrally controlled sensor networksJuly 10, 2007

SASO 200720• Thank you for your attention

July 10, 2007

SASO 2007

214