Transcript Scheduling of Collision-free Broadcast in Ad Hoc Networks

Delay-efficient Data Gathering in
Sensor Networks
Bin Tang, Xianjin Zhu and Deng Pan
1
Outline

Introduction

Problem Statement

Data Gathering Algorithms

Conclusions
2
Introduction

Data gathering in sensor networks



Time critical applications




To explore energy efficiency
To explore data correlation and redundancy
Patient Monitoring
Surveillance sensor networks
Fine-grained environmental monitoring
Delay Efficiency is the goal of our work.
3
Our assumptions



One half duplex interface
Collision free – each node can not receive more
than one transmissions
Each node can HEAR more than one transmissions
1

2
3
4
5
Each node (except sink) has one message
4
S
Problem Statement

Disk graph G=(V,E)



sink node S
Each node (except S) has one message
Delay-efficient Data Gathering problem:
Schedule the collision-free message transmission for each
node, s.t. the delay when all messages are received by S
is minimized.

Minimum delay is 7 time slots
5
Our Solution

Linear Topology

Star Topology

NP-completeness

Tree Topology

General Topology
6
Linear Topology

Divide the nodes into two sets, so that all the nodes
in each set can transmit simultaneously
N=4
4
3
2
1
sink
Odd={1,3}, Even={2,4}
7
Linear Topology: Proof of Optimum


Step 1: Delay of above algorithm is 2N-1, where N is
the number of nodes (excluding sink)
Step 2: 2N-1 is the lower bound of delay in linear
topology



For messages from node 2, 3, …, N: 2 slots are needed to
pass through node 1, for each message
For message from node 1: 1 slot is needed to send to sink
Total delay≥2(N-1)+1=2N-1
N

N-1
2
1
sink
Thus, our algorithm is optimal
8
Star Topology

In order to achieve the minimum delay, different
branches need to be pipelined
sink
9
Star Topology



More branches?
Divide the branches into two groups, so that each
group has equal number of nodes
How to divide branches into 2 equal-set? NP-hard
10
Star Topology: NP-complete


Prove that our problem is NP-complete by reduction
from the Integer Partition problem
Integer Partition:

Give a set of integers X={x1,x2,…,xn} and a target y. Is
there a subset X’ of X, such that the sum of all the elements
in X’ is equal to y?
11
Star Topology: NP Reduction

For each xi, create a branch with xi nodes

Create another branch with (∑X-2y) nodes

Connect all the branches with the sink

For the created star topology graph, is its minimum
gathering delay 2(∑X-y)?
12
Star Topology: NP Reduction
13
Star Topology: NP Complete

If the integer partition problem has a solution, say
X=X’∪X’’, X’∩X’’={}, and ∑X’=y. Then, the minimum
gathering delay of the created graph is 2(∑X-y)

Since ∑X’+ (∑X-2y) =(∑X+ (∑X-2y) )/2

Similarly, vice versa
14
Tree Topology


For the tree topology, if the root has only one child, it
can be viewed as the conjunction of several lines.
Similarly, minimum delay = (2N-1), where k is the
number of nodes in the sub-tree
15
Tree Topology

How about if the root has more than one child?
Similar to the star topology with multiple branches
16
General Topology



Generate a BFS tree, the general graph can be
processed as a tree topology.
Heuristics to divide the BFS tree into two parts with
similar number of nodes.
The maximal gathering delay has an upper bound of
2N-1, and the optimal delay is at least N. So our
solution is a 2-approximation algorithm
17
Conclusions

Current status





Formulate the collision-free data gathering
problem
There is optimal algorithm in linear topology
In tree/star/general graph, our problem is NPcomplete
2 approximation algorithm in general graph
Future work


Distributed algorithms
Simulation
18