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:
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.