Fast Data Collection in
Tree-Based Wireless Sensor Networks
ABSTRACT:
We investigate the following fundamental
question—how fast can information be collected from a wireless sensor network organized
as tree? To address this, we explore and evaluate a number of different
techniques using realistic simulation models under the many-to-one
communication paradigm known as convergecast. We first consider time scheduling
on a single frequency channel with the aim of minimizing the number of time
slots required (schedule length) to complete a convergecast. Next, we combine scheduling
with transmission power control to mitigate the effects of interference, and
show that while power control helps in reducing the schedule length under a
single frequency, scheduling transmissions using multiple frequencies is more
efficient. We give lower bounds on the schedule length when interference is
completely eliminated, and propose algorithms that achieve these bounds. We also
evaluate the performance of various channel assignment methods and find
empirically that for moderate size networks of about
100 nodes, the use of multifrequency
scheduling can suffice to eliminate most of the interference. Then, the data
collection rate no longer remains limited by interference but by the topology
of the routing tree. To this end, we construct degree-constrained spanning trees
and capacitated minimal spanning trees, and show significant improvement in
scheduling performance over different deployment densities. Lastly, we evaluate
the impact of different interference and channel models on the schedule length.
ARCHITECTURE:
ALGORITHM
USED:
1. BFSTIMESLOTASSIGNMENT.
2. LOCAL-TIMESLOTASSIGNMENT
Algorithm 1
BFS-TIMESLOTASSIGNMENT
1. Input: T = (V, ET )
2. While ET _= φ do
3. e ← next edge from ET in BFS order
4. Assign
minimum time slot t to edge e respecting adjacency and
interfering constraints
5. ET ← ET \ {e}
6. end while
Algorithm 2
LOCAL-TIMESLOTASSIGNMENT
1. node.buffer = full
2. if {node is sink} then
3. Among
the eligible top-subtrees, choose the one with the largest
number of
total (remaining) packets, say top-subtree i
4. Schedule
link (root(i), s) respecting interfering constraint
5. else
6. if {node.buffer == empty} then
7. Choose a
random child c of node whose buffer is full
8. Schedule
link (c, node) respecting
interfering constraint
9. c.buffer = empty
10. node.buffer = full
11. end if
12. end if
EXISTING
SYSTEM:
Existing
work had the objective of minimizing the completion time of converge casts.
However, none of the previous work discussed the effect of multi-channel
scheduling together with the comparisons of different channel assignment
techniques and the impact of routing trees and none considered the problems of
aggregated and raw converge cast, which represent two extreme cases of data
collection,
DISADVANTAGES
OF EXISTING SYSTEM:
In the existing system, it addressed the
fundamental limitations due to interference and half-duplex transceivers on the
nodes.
PROPOSED
SYSTEM:
Fast data
collection with the goal to minimize the schedule length for aggregated
converge cast has been studied by us in, and also by others in, we
experimentally investigated the impact of transmission power control and
multiple frequency channels on the schedule length
Our present
work is different from the above in that we evaluate transmission power control
under realistic settings and compute lower bounds on the schedule length for
tree networks with algorithms to achieve these bounds. We also compare the
efficiency of different channel assignment methods and interference models, and
propose schemes for constructing specific routing tree topologies that enhance
the data collection rate for both aggregated and raw-data converge cast.
ADVANTAGES
OF PROPOSED SYSTEM:
In the proposed system, we construct
degree-constrained spanning trees and capacitated minimal spanning trees, and
show significant improvement in scheduling performance over different
deployment densities.
MODULES:
1. Periodic Aggregated Converge cast.
2. Transmission Power Control
3. Aggregated Data Collection
4. Raw Data Collection
5. Tree-Based Multi-Channel Protocol (TMCP)
MODULE DESCRIPTION:
1. Periodic
Aggregated Converge cast.
Data aggregation is a commonly used technique in WSN that
can eliminate redundancy and minimize the number of transmissions, thus saving
energy and improving network lifetime. Aggregation can be performed in many
ways, such as by suppressing duplicate messages; using data compression and
packet merging techniques; or taking advantage of the correlation in the sensor
readings
We consider continuous monitoring applications where
perfect aggregation is possible, i.e., each node is capable of aggregating all
the packets received from its children as well as that generated by itself into
a single packet before transmitting to its parent. The size of aggregated data
transmitted by each node is constant and does not depend on the size of the raw
sensor readings.
2. Transmission
Power Control
We evaluate the impact of transmission power control,
multiple channels, and routing trees on the scheduling performance for both
aggregated and raw-data converge cast.. Although the techniques of transmission power control and
multi-channel scheduling have been well studied for eliminating interference in
general wireless networks, their performances for bounding the completion of
data collection in WSNs have not been explored in detail in the previous
studies. The fundamental novelty of our approach lies in the extensive
exploration of the efficiency of transmission power control and multichannel
communication on achieving fast converge cast operations in WSNs.
3. Aggregated Data Collection
We augment their scheme with a new set of rules and grow
the tree hop by hop outwards from the sink. We assume that the nodes know their
minimum-hop counts to sink.
4. Raw
Data Collection
The data collection rate often no longer remains limited
by interference but by the topology of the network. Thus, in the final step, we
construct network topologies with specific properties that help in further
enhancing the rate. Our primary conclusion is that, combining these different
techniques can provide an order of magnitude improvement for aggregated
converge cast, and a factor of two improvement for raw-data converge cast,
compared to single-channel TDMA scheduling on minimum-hop routing trees.
5. Tree-Based Multi-Channel
Protocol (TMCP)
Fig: Schedule generated with TMCP
TMCP is a greedy, tree-based,
multi-channel protocol for data collection applications. It partitions the
network into
multiple sub trees and minimizes the intra
tree interference by assigning different channels to the nodes
residing on different branches starting from the top to the
bottom of the tree. Figure shows the same tree given in Fig. which is scheduled according to TMCP
for aggregated data collection. Here, the nodes on the
leftmost branch is assigned frequency F1,
second branch
is assigned frequency F2 and the
last branch is assigned frequency F3 and after the channel assignments, time
slots are assigned to the nodes with the BFSTimeSlotAssignment algorithm.
Advantage
Advantage of TMCP
is that it is designed to support converge cast traffic and does not require
channel switching. However, contention inside the branches is not resolved
since all the nodes on the same branch communicate on the same channel
SYSTEM CONFIGURATION:-
HARDWARE REQUIREMENTS:-
ü Processor -Pentium –III
ü Speed - 1.1 Ghz
ü RAM - 256 MB(min)
ü Hard
Disk - 20 GB
ü Floppy
Drive - 1.44 MB
ü Key
Board - Standard Windows Keyboard
ü Mouse - Two or Three Button Mouse
ü Monitor - SVGA
SOFTWARE REQUIREMENTS:-
v Operating System : Windows95/98/2000/XP
v Front End : Java / J2ME/ APPLET
v Simulation : Sun Java Wireless Toolkit
REFERENCE:
O¨ zlem Durmaz Incel, Amitabha Ghosh,
Bhaskar Krishnamachari, and Krishnakant Chintalapudi, “Fast Data Collection in
Tree-Based Wireless Sensor Networks”, IEEE
TRANSACTIONS ON MOBILE COMPUTING, VOL. 11, NO. 1, JANUARY 2012.