Local
Broadcast Algorithms in Wireless Ad Hoc Networks: Reducing the Number of
Transmissions
ABSTRACT:
There are two
main approaches, static and dynamic, to broadcast algorithms in wireless ad hoc
networks. In the static approach, local algorithms determine the status
(forwarding/non-forwarding) of each node proactively based on local topology information
and a globally known priority function. In this paper, we first show that local
broadcast algorithms based on the static approach cannot achieve a good
approximation factor to the optimum solution (an NP-hard problem). However, we
show that a constant approximation factor is achievable if (relative) position
information is available. In the dynamic approach, local algorithms determine
the status of each node “on-the-fly” based on local topology information and
broadcast state information. Using the dynamic approach, it was recently shown
that local broadcast algorithms can achieve a constant approximation factor to
the optimum solution when (approximate) position information is available.
However, using position information can simplify the problem. Also, in some
applications it may not be practical to have position information. Therefore,
we wish to know whether local broadcast algorithms based on the dynamic
approach can achieve a constant approximation factor without using position
information. We answer this question in the positive - we design a local
broadcast algorithm in which the status of each node is decided “on-the-fly”
and prove that the algorithm can achieve both full delivery and a constant approximation
to the optimum solution.
ARCHITECTURE:
ALGORITHM:
HYBRID ALGORITHM:
The proposed broadcast algorithm is
a hybrid algorithm, hence every node that broadcasts the message may select
some of its neighbors to forward the message. In our proposed broadcast
algorithm, every broadcasting node selects at most one of its neighbors. A node
has to broadcast the message if it is selected to forward. Other nodes that are
not selected have to decide whether or not to broadcast on their own. This
decision is made based on a self-pruning condition called the coverage
condition.
ALGORITHM:
1: Extract ids
of the broadcasting node and the selected node from the received message m
2: if u has
broadcast the message m before then
3: Discard the
message
4: Return
5: end if
6: if u receives
m for the 􀂿rst
time then
7: Create and 􀂿ll
the list Listcov u (m)
8: end if
9: Update the
list Listcov u (m)
10: Remove the
information added to the message by the previous broadcasting node
11: if Listcov
u (m) _= ∅ then
12: Select an id
from Listcov u (m) and add it to the message
13: Schedule the
message {(*only update the
selected id if m is already in the queue*)}
14: else {(*Listcov u (m) = ∅ in this case*)}
15: if u was
selected then
16: Schedule the
message {(*only remove the id
of the selected neighbor if m is already in the queue*)}
17: else
18: Remove the
message form the queue if u has not been selected by any node before
19: end if
20: end if
AIM & OBJECTIVE:
To reduce the number of
transmission and also to reduce the energy consumption using local broadcast
algorithm
To analyze the effect using two
proposed approaches static and dynamic broadcasting
PROBLEM STATEMENT:
PROBLEM STATEMENT:
Broadcasting can be achieved
through flooding, in which every node transmits the message after receiving it
for the first time. However, flooding can impose a large number of redundant
transmissions, which can result in significant waste of constrained resources
such as bandwidth and power. In general, not every node is required to
forward/transmit the message in order to deliver it to all nodes in the
network.
EXISTING SYSTEM:
The existing local broadcast
algorithms can be classified based on whether the forwarding nodes are
determined statically (based on only local topology information) or dynamically
(based on both local topology and broadcast state information). In the static
approach, the distinguishing feature of local algorithms over other broadcast
algorithms is that using local algorithms any local topology changes can affect
only the status of those nodes in the vicinity. Therefore, local algorithms can
provide scalability as the constructed CDS can be updated, efficiently. The
existing local algorithms in this category typically use a priority function
known by all nodes in order to determine the status of each node. In this paper
we show that, using only local topology information and a globally known
priority function, the local broadcast algorithms based on the static approach
are not able to guarantee a good approximation factor to the optimum solution
(i.e., MCDS). On the other hand, we show that local algorithms based on the
static approach can achieve interesting results such as a constant
approximation factor and shortest path preservation if the nodes are provided
with position information.
DISADVANTAGES
OF EXISTING SYSTEM:
1. Minimum number of transmission
will be Possible.
2. All the Nodes have been static.
3. Data loss problem occurred.
PROPOSED SYSTEM:
In the dynamic approach, the status of
each node (hence the CDS) is determined “on-the-fly” during the broadcast
progress. Using this approach, the constructed CDS may vary from one broadcast
instance to another even when the whole network topology and the source node
remain unchanged. Consequently, the broadcast algorithms based on the dynamic
approach typically have small maintenance cost and are expected to be robust
against node failures and network topology changes. Many local broadcast
algorithms in this category use local neighbor information to reduce the total
number of transmissions and to guarantee full delivery (assuming no loss at the
MAC/PHY layer). If only selected node will be forward the message.
ADVANTAGES
OF PROPOSED SYSTEM:
1. Local broadcast
algorithms in reducing the total number of transmissions.
2. Full delivery
and constant approximation to the optimum solution.
3. Avoid
forwarding/rebroadcasting a message.
4. Hybrid
algorithm.
5. Node’s are
dynamic.
6. Calculate
Maximum and Minimum transmission range of the nodes in the network.
MODULES:
·
Mobile Ad Hoc Network
·
Static Approach
·
Dynamic Approach
·
Self Pruning
·
Network Model
MODULES DESCRIPTION:
Mobile Ad Hoc Network
Wireless ad hoc networks
have emerged to support applications, in which it is required / desired to have
wireless communications among a variety of devices without relying on any
infrastructure or central management. In ad hoc networks, wireless devices, simply
called nodes, have limited transmission range. Therefore, each node can
directly communicate with only those within its transmission range (i.e., its
neighbors) and requires other nodes to act as routers in order to communicate
with out-of-range destinations.
Static Approach
The existing local broadcast
algorithms can be classified based on whether the forwarding nodes are
determined statically (based on only local topology information) or dynamically
(based on both local topology and broadcast state information). In the static
approach, the distinguishing feature of local algorithms over other broadcast
algorithms is that using local algorithms any local topology changes can affect
only the status of those nodes in the vicinity. Therefore, local algorithms can
provide scalability as the constructed CDS can be updated, effciently. The
existing local algorithms in this category typically use a priority function
known by all nodes in order to determine the status of each node
Dynamic Approach
In the dynamic approach, the
status of each node (hence the CDS) is determined “on-the-fly” during the
broadcast progress. Using this approach, the constructed CDS may vary from one
broadcast instance to another even when the whole network topology and the
source node remain unchanged. Consequently, the broadcast algorithms based on
the dynamic approach typically have small maintenance cost and are expected to
be robust against node failures and network topology changes. Many local
broadcast algorithms in this category use local neighbor information to reduce
the total number of transmissions and to guarantee full delivery.
Self Pruning
In neighbor designating
algorithms, each forwarding node selects some of its local neighbors to forward
the message. Only the selected nodes are then required to forward the message
in the next step. In self-pruning
algorithms on the other hand, each node decides by itself whether or not to
forward a message. The decision is made based on a self-pruning condition. For
example, a simple self-pruning condition employed in is whether all neighbors
have been covered by previous transmissions. In other words, a node can avoid
forwarding/rebroadcasting a message if all of its neighbors have received the
message by previous transmissions.
Network Model
The proposed algorithm based
on the dynamic approach can be extended to the case where the nodes have
different transmission ranges. In this case, it can be proved that the
algorithm guarantees a constant approximation. The maximum transmission range
and RMin is the minimum transmission range of the nodes in the network and two
nodes have a link iff both are in transmission range of each other.
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 TOOL USED : NETBEANS IDE 7.0
v Front End : JAVA
REFERENCES:
Majid Khabbazian, Blake, Vijay K.
Bhargava, “Local Broadcast Algorithms in Wireless Ad Hoc Networks: Reducing the
Number of Transmissions”, IEEE
TRANSACTIONS ON MOBILE COMPUTING, VOL 11, NO.3, MARCH 2013.
