Periodic Beaconing For Geographic Routing Computer Science Essay

In geographic routing, nodes need to maintain up-to-date positions of their immediate neighbors for making effective forwarding decisions. Periodic broadcasting of beacon packets that contain the geographic location coordinates of the nodes is a popular method used by most geographic routing protocols to maintain neighbor positions. To demonstrate the periodic beaconing regardless of the node mobility and traffic patterns in the network is not attractive from both update cost and routing performance points of view. Adaptive Position Update (APU) strategy for geographic routing, which dynamically adjusts the frequency of position updates based on the mobility dynamics of the nodes and the forwarding patterns in the network. APU is based on two simple principles: (i) nodes whose movements are harder to predict update their positions more frequently (and vice versa), and (ii) nodes closer to forwarding paths update their positions more frequently (and vice versa). It is validated by NS2 simulations of a well known geographic routing protocol, Greedy Perimeter Stateless Routing Protocol (GPSR), shows that APU can significantly reduce the update cost and improve the routing performance in terms of packet delivery ratio and average end-to-end delay in comparison with periodic beaconing and other recently proposed updating schemes. The benefits of APU are further confirmed by undertaking evaluations in realistic network scenarios, which account for localization error, realistic radio propagation and sparse network.

CHAPTER 1

INTRODUCTION

OVERVIEW

1.1.1 ADHOC NETWORKS:

"Ad Hoc" is actually a Latin phrase that means "for this purpose". It is often used to describe solutions that are developed on-the-fly for a specific purpose. In computer networking, an ad hoc network refers to a network connection established for a single session and does not require a router or a wireless base station.

Laptop

Computer

Laptop

Figure 1.1.1 Adhoc networks

If it is need transfer a file to other laptop, it will create an adhoc network between one computer and other laptop to transfer the file. This may be done using an Ethernet crossover cable, or the computers' wireless cards to communicate with each other. If it is need to share files with more than one computer, it can set up a mutlihop adhoc network, which can transfer data over multiple nodes.

An Adhoc network is a wireless host can communicate with each other without fixed infrastructure. The adhoc network is a temporary network connection created for a specific purpose. If the network is set up for a longer period of time, it is just a plain old local area network. Eg: Bluetooth, WLAN

Advantages:

It is easy to set up.

It has no access points during information passing between two nodes, so it is cheaper.

Disadvantages:

It is unsecured network.

It has limited resources.

1.1.2. MOBILE ADHOC NETWORK (MANET):

A mobile adhoc network is a self-configuring infrastructureless network of mobile devices connected by wireless. Each device in a MANET is free to move independently in any direction, and will therefore change its links to other devices frequently. The primary challenge in building a MANET is equipping each device to continuously maintain the information required to properly route traffic. Such networks may operate by themselves or may be connected to the larger internet. It will change its links to other devices frequently. Topology changes rapidly.

To accommodate the changing topology special routing algorithms are needed. For relatively small networks flat routing protocols may be sufficient. However, in larger networks either hierarchical or geographic routing protocols are needed. There is no single protocol that fits all networks perfectly.

The protocols have to be chosen according to network characteristics, such as density, size and the mobility of the nodes. MANET does not require any fixed infrastructure, such as a base station, therefore, it is an attractive option for connecting devices quickly and spontaneous.

Mobile

Figure 1.1.2 Mobile adhoc network

Mobile Ad Hoc Networks (MANETs) provide communication between all nodes in the network topology without the presence of a centralized authority. Since the nodes communicate over wireless links, they have to contend with the effects of radio communication, such as noise, fading, and interference. In addition, the links typically have less bandwidth than a wired network. Each node in a wireless ad hoc network functions as both a host and a router, and the control of the network is distributed among the nodes.

The network topology is in general dynamic, because the connectivity among the nodes may vary with time due to node departures, new node arrivals, and the possibility of having mobile nodes. Nodes can perform the roles of both hosts and routers. No centralized controller and infrastructure. It has Intrinsic mutual trust. It has Dynamic network topology. It can be setup anywhere. It has limited security. They provide access to information and services regardless of geographic position.

Mobile Ad Hoc Networks consist of nodes that change position frequently. To accommodate the changing topology special routing algorithms are needed. Flat routing protocols may be sufficient in small networks. Geographic routing protocols are needed in larger networks. There is no single protocol that fits all networks perfectly. The protocols have to be chosen according to network characteristics, such as density, size and the mobility of the nodes.

Mobile ad hoc networking is one of the more innovative and challenging areas of wireless networking. It consists of devices that are autonomously self-organizing in networks, adhoc networks offer a large degree of freedom at a lower cost than other networking solutions.

Simulations of MANET:

There are several ways to study MANETs. One solution is the use of simulation tools like OPNET, Netsim and NS2.

Advantages of MANET:

Networks can be set up at any place and time.

The networks work without any pre-existing infrastructure.

Its nodes have mobility.

It is light equipment.

Disadvantages of MANET:

It has limited resources.

It has limited physical security.

Lack of authorization facilities.

Applications of MANET:

Military or police exercises,

Fire brigades.

Disaster relief operations.

LITERATURE SURVEY

1.2.1. Greedy perimeter stateless routing for wireless networks:

Greedy Perimeter Stateless Routing (GPSR), a novel routing protocol for wireless datagram networks that uses the positions of routers and a packet's destination to make packet forwarding decisions. GPSR makes greedy forwarding decisions using only information about a router's immediate neighbors in the network topology.

When a packet reaches a region where greedy forwarding is impossible, the algorithm recovers by routing around the perimeter of the region. GPSR scales better in per router state than shortest path and ad-hoc routing protocols as the number of network destinations increases.

GPSR can use local topology information to find correct new routes quickly. GPSR protocol use extensive simulation of mobile wireless networks to compare its performance with Dynamic Source Routing. In networks of wireless stations, communication between source and destination nodes may require traversal of multiple hops, as radio ranges are finite.

A community of adhoc network researchers has proposed, implemented, and measured a variety of routing algorithms for such networks. The observation that topology changes more rapidly on a mobile, wireless network than on wired networks, where Link State Protocol is used.

In a link-state protocol, the only information passed between the nodes is information used to construct the connectivity maps. GPSR benefits from geographic routing use of only immediate-neighbor information in forwarding decision. GPSR allows nodes to figure out who its closest neighbors are also close to the destination the information is supposed to travel.

1.2.2. BLR: Beacon-Less Routing Algorithm for Mobile Ad-Hoc Networks:

Routing of packets in mobile ad-hoc networks with a large number of nodes or with high mobility is a very difficult task and current routing protocols do not really scale well. The Beacon-Less Routing Algorithm (BLR) is a routing protocol that makes use of location information to reduce routing overhead. BLR does not require nodes to periodically broadcast Hello-messages (called beaconing), and thus avoids drawbacks such as extensive use of scarce battery-power, interferences with regular data transmission, and performance degradation.

BLR selects a forwarding node in a distributed manner among all its neighboring nodes with having information neither about their positions nor even about their existence. Data packets are broadcasted and the protocol takes care that just one of the receiving nodes forwards the packet. Optimized forwarding is achieved by applying a concept of Dynamic Forwarding Delay (DFD). Consequently, the node which computes the shortest forwarding delay relays the packet. This forwarding is detected by the other nodes and suppresses them to relay the same packet any further. Analytical results and simulation experiments indicate that BLR provides efficient and robust routing in highly dynamic mobile ad-hoc networks.

A wireless mobile ad-hoc network operates without any centralized administration and does not rely on any infrastructure. Instead the network is completely self-organizing and the communication is maintained on a peer-to-peer basis between the mobile hosts. If two hosts wish to communicate are not within range, their intermediate nodes act as relay stations. Due to the mobility of the nodes, changes to the network topology may be frequent and unpredictable.

The nodes suddenly be switched on, causing new links to appear and vanish. Routing in such a dynamic environment is a difficult task. The Beacon-Less Routing algorithm (BLR) performs routing in a distributed manner without information about neighboring nodes.

1.2.3. Efficient geographic routing in multihop wireless networks:

A new link metric normalized advance (NADV) for geographic routing in multihop wireless networks. NADV selects neighbors with the optimal trade-off between proximity and link cost. Coupled with the local next hop decision in geographic routing, NADV enables an adaptive and efficient cost-aware routing strategy. Depending on the objective or message priority, applications can use the NADV framework to minimize various types of link cost.

The efficient methods for link cost estimation and perform detailed simulation. NADV out performs current schemes in many aspects, high noise environments with frequent packet losses, the use of NADV leads to 81% higher delivery ratio. When compared to centralized routing under certain settings, geographic routing using NADV paths whose cost is close to the optimum.

NADV for efficient geographic routing. Although a few recent geographic routing schemes consider link costs in the next hop selection, they are limited to one specific object, the NADV framework can accommodate a variety of different cost types.

Depending on system objectives or message priority, applications can use the NADV framework to take different routing strategies. An urgent message can be routed along the path that minimizes the end-to-end latency, and a low-priority message may take a path that minimizes power consumption to increase the overall network lifetime. Each transmission requires high network bandwidth as well as node resources, high-cost links and causes more retransmissions due to packet errors.

NADV techniques for efficient and adaptive link cost estimation. It provides multiple techniques thus enabling nodes to choose the best scheme for the current network and system setting. In a resource network, nodes can use a method that uses probe messages. In the dense large-scale network with limited resources, such probe messages may prove to be costly, and nodes can use an alternate scheme that uses no extra control messages.

NADV, a link metric for geographic routing in multihop wireless networks. Geographic routing with NADV provides an adaptive routing strategy, which can be used for various link cost types. Techniques for link cost estimation. In the simulation experiments, the combination of NADV and cost estimation techniques outperforms the current geographic routing scheme. NADV also finds paths whose cost is close to the optimum. Cost-aware routing schemes including NADV benefit greatly from fast and accurate link cost estimation.

1.2.4. Geographic Random Forwarding (GeRaF) for Ad Hoc and sensor Networks: Multihop Performance:

A novel forwarding technique based on geographical location of the nodes involved and random selection of the relaying node via contention among receivers. The multihop performance of such a solution, in terms of the average number of hops to reach a destination as a function of the distance and of the average number of available neighbors.

Ad hoc and sensor networks are currently attracting a lot of interest in the research community. One of the main issues is to save the energy since the nodes are usually battery powered and need to be alive for a relatively long time. A node can save substantial energy is by powering off the radio since transmitting, receiving, and listening to an idle channel are functions which requires a comparable amount of power.

MAC and routing strategies need to be revisited since CSMA-based access schemes need all nodes to continuously listen to the channel while nodes power off their radio may end up not being reachable and aware of activity in the network. The main problem is that combining protocols which minimize the amount of time of the radio with effective strategies for MAC and routing. Geographic Random Forwarding (GeRaF, pronounced as "giraffe"), a novel transmission scheme based on geographical routing where packets are relayed on a best-effort basis.

CHAPTER 2

WORK DONE IN PHASE ONE

2.1 SYSTEM ARCHITECTURE DESIGN:

Network Model

Beacon Interval Generation

APU Analysis Module

Forwarding Strategy

Beacon Internal Adjustment

Beacon Update Module

Geographic Routing

Route Management

Figure 2.1 System architecture design

2.2 FEATURE EXTRACTION:

The geographic routing protocols require the following information:

the position of the final destination of the packet and

the position of a node's neighbors.

The former can be obtained by querying a location service such as the Grid Location System. Each node exchanges its own location information with its neighboring nodes. This allows each node to build a local map of the nodes within its vicinity, often referred to as the local topology.

The nodes are mobile or when nodes often switch off and on, the local topology rarely remains static. Hence, it is necessary that each node broadcasts its updated location information to all of its neighbors. These location update packets are usually referred to as beacons. In most geographic routing protocols, beacons are broadcast periodically for maintaining an accurate neighbor list at each node.

Position updates are costly in many ways. Each update consumes node energy, wireless bandwidth, and increases the risk of packet collision at the medium access control (MAC) layer. Packet collisions cause packet loss which in turn affects the routing performance due to decreased accuracy in determining the correct local topology. A lost data packet does get retransmitted, but at the expense of increased end-to-end delay.

CHAPTER 3

SYSTEM ORGANIZATION

3.1 DATA FLOW DIAGRAM:

LEVEL 0:

Network Model

Setup the systems

Identify the speed limit

Set up the configurations

LEVEL 1:

Routing process

Identify the final destinations

Identify the position of neighbor node

LEVEL 2:

Beacon model

Identify the neighboring node

Message updating

LEVEL 3:

APU analysis

Analysis for Beacon overhead

Analysis for unknown neighbor's ratio

Analysis for false neighbor ratio

Energy Consumption

Figure 3.1 Dataflow diagram

3.2 USECASE DIAGRAM:

Configure the networks

Identify the neighboring node

Beacon updating process

â€¦â€¦â€¦â€¦â€¦â€¦â€¦â€¦â€¦â€¦â€¦..

Send the data

Client

Server

Neighbor 1

Neighbor 2

Neighbor n

Figure 3.2 Usecase diagram

CHAPTER 4

MODULES DESCRIPTION

Classification of modules:

4.1 Network Model

4.2 Geographic Routing

4.3 Beacon Update Module

4.4 APU Analysis Module

4.1 Network model:

Network model is the arrangement of nodes of a computer. It is the topology structure of a network, and may be depicted physically or logically. Physical topology refers to the placement of the network's various components, including device location and cable installation. Logical topology shows how data flows within a network. Distances between nodes, physical interconnections, transmission rates, and signal types may differ between two networks, though their topologies may be identical.

Network models can be components of other network models, thereby enabling the construction of multi-level systems. This model does not directly define new dynamic behavior. The dynamics of a network model are determined by the dynamics of its component parts and their interactions. Network models define structure.

4.2 Geographic routing:

Geographic routing is also called georouting or position based routing which is a routing principle that relies on geographic position information. It is mainly proposed for wireless networks and based on the idea that the source sends a message to the geographic location of the destination instead of using the network address.

The idea of using position information in the area of packet radio networks and interconnection networks. Geographic routing requires that each node can determine its own location and that the source is aware of the location of the destination. With this information a message can be routed to the destination without knowledge of the network topology or a prior route discovery.

Routing

4.3 Beacon Update Module:

The nodes are mobile or when nodes often switch off and on, the local topology rarely remains static. It is necessary that each node broadcasts its updated location information to all of its neighbors. These location update packets are usually referred to as beacon update module. In most geographic routing protocols, beacon update is broadcast periodically for maintaining an accurate neighbor list at each node.

Position updates are costly in many ways. Each update consumes node energy, wireless bandwidth, and increases the risk of packet collision at the medium access control (MAC) layer. Packet collisions cause packet loss which in turn affects the routing performance due to decreased accuracy in determining the correct local topology. The beacon update plays an important part in maintaining an accurate representation of the local topology. A lost data packet does get retransmitted, but at the expense of increased end-to-end delay.

4.4 APU Analysis Module:

Adaptive Position Update (APU) analysis adapts the beacon update intervals to the mobility dynamics of the nodes and the amount of data being forwarded in the neighborhood of the nodes. APU eliminates the drawbacks of periodic beaconing by adjusts the beacon update intervals dynamically based on the mobility dynamics of the nodes which contain their current position and speed. If the predicted location of node is different from the actual location of node, a new beacon is broadcast to inform the neighbors about changes in the node's mobility.

An accurate representation of the local topology is desired at the nodes that are responsible for forwarding packets. The local topology accuracy is collectively measured by the following two metrics:

Unknown neighbor Ratio

False neighbor ratio

Figure 4.4.1 Unknown neighbor ratio and False neighbor ratio.

â€¢ Unknown neighbor Ratio: This is defined as the ratio of the new neighbors a node is not aware of, but that are within the radio range of the node to the total number of neighbors. This leads to sub-optimal routing decisions.

â€¢ False neighbor Ratio: This is defined as the ratio of obsolete neighbors that are in the neighbor list of a node, but it is already moved out of the node's radio range to the total number of neighbors. Its retransmission leads to waste bandwidth and increase the delay.

The unknown neighbors of a node are the new neighbors that are moved into the radio range of this node and are absent from node's neighbor node. The false neighbors of a node are the neighbors that exist in the node's neighbor table and moved out from the node's radio range. The existence of both unknown and false neighbors impacts the performance of the geographic routing protocol.

CHAPTER 5

IMPLEMENTATION AND RESULTS

5.1 TECHNIQUES USED:

5.1.1 Mobility Prediction (MP) Rule:

This MP rule adapts the beacon generation rate to the frequency with which the nodes change the characteristics that govern their motion (velocity). The motion characteristics are included in the beacons broadcast to a node's neighbors. The neighbors can then track the node's motion using simple linear motion equations.

Nodes that frequently change their motion need to frequently update their neighbors, since their locations are changing dynamically. Nodes which move slowly do not need to send frequent updates. A periodic beacon update policy cannot satisfy both these requirements simultaneously, since a small update interval will be wasteful for slow nodes, whereas a larger update interval will lead to inaccurate position information for the highly mobile nodes.

5.1.2 On-Demand Learning (ODL) Rule :

A node broadcasts beacons response to data forwarding activities that occur in the vicinity of that node. Whenever a node overhears a data transmission from a new neighbor, it broadcasts a beacon as a response, it implies a neighbor who is not contained in the neighbor list of this node. A node waits for a small random time interval before responding with the beacon to prevent collisions with other beacons. The location updates are piggybacked on the data packets and that all nodes operate in the promiscuous mode, which allows them to overhear all data packets transmitted in their vicinity. Since the data packet contains the location of the final destination, any node that overhears a data packet also checks its current location and determines if the destination is within its transmission range.

5.2 Coding:

# Provide initial location of mobile nodes

$node_(0) set X_ 5.0

$node_(0) set Y_ 5.0

$node_(0) set Z_ 0.0

$node_(1) set X_ 240.0

$node_(1) set Y_ 265.0

$node_(1) set Z_ 0.0

$node_(2) set X_ 150.0

$node_(2) set Y_ 240.0

$node_(2) set Z_ 0.0

$node_(3) set X_ 20.0

$node_(3) set Y_ 20.0

$node_(3) set Z_ 0.0

$node_(4) set X_ 200.0

$node_(4) set Y_ 120.0

$node_(4) set Z_ 0.0

$node_(5) set X_ 150.0

$node_(5) set Y_ 20.0

$node_(5) set Z_ 0.0

$node_(6) set X_ 35.0

$node_(6) set Y_ 120.0

$node_(6) set Z_ 0.0

$node_(7) set X_ 100.0

$node_(7) set Y_ 20.0

$node_(7) set Z_ 0.0

$node_(8) set X_ 80.0

$node_(8) set Y_ 130.0

$node_(8) set Z_ 0.0

$node_(9) set X_ 170.0

$node_(9) set Y_ 200.0

$node_(9) set Z_ 0.0

# Generation of movements

$ns at 10.0 "$node_(0) setdest 250.0 250.0 3.0"

$ns at 15.0 "$node_(1) setdest 45.0 285.0 5.0"

$ns at 110.0 "$node_(0) setdest 230.0 290.0 5.0"

# Set a TCP connection between node_(0) and node_(1)

set tcp [new Agent/TCP/Newreno]

$tcp set class_ 2

set sink [new Agent/TCPSink]

$ns attach-agent $node_(0) $tcp

$ns attach-agent $node_(1) $sink

$ns connect $tcp $sink

set ftp [new Application/FTP]

$ftp attach-agent $tcp

$ns at 10.0 "$ftp start"

$ns at 25.0 "$ftp stop"

set tcp [new Agent/TCP/Newreno]

$tcp set class_ 2

set sink [new Agent/TCPSink]

$ns attach-agent $node_(2) $tcp

$ns attach-agent $node_(5) $sink

$ns connect $tcp $sink

set ftp [new Application/FTP]

$ftp attach-agent $tcp

$ns at 30.0 "$ftp start"

$ns at 45.0 "$ftp stop"

set tcp [new Agent/TCP/Newreno]

$tcp set class_ 2

set sink [new Agent/TCPSink]

$ns attach-agent $node_(3) $tcp

$ns attach-agent $node_(6) $sink

$ns connect $tcp $sink

set ftp [new Application/FTP]

$ftp attach-agent $tcp

$ns at 50.0 "$ftp start"

$ns at 80.0 "$ftp stop"

set tcp [new Agent/TCP/Newreno]

$tcp set class_ 2

set sink [new Agent/TCPSink]

$ns attach-agent $node_(4) $tcp

$ns attach-agent $node_(8) $sink

$ns connect $tcp $sink

set ftp [new Application/FTP]

$ftp attach-agent $tcp

$ns at 90.0 "$ftp start"

$ns at 120.0 "$ftp stop"

set tcp [new Agent/TCP/Newreno]

$tcp set class_ 2

set sink [new Agent/TCPSink]

$ns attach-agent $node_(0) $tcp

$ns attach-agent $node_(9) $sink

$ns connect $tcp $sink

set ftp [new Application/FTP]

$ftp attach-agent $tcp

$ns at 120.0 "$ftp start"

# Define node initial position in nam

for {set i 0} {$i < $val(nn)} { incr i } {

# 30 defines the node size for nam

$ns initial_node_pos $node_($i) 30

}

# Telling nodes when the simulation ends

for {set i 0} {$i < $val(nn) } { incr i } {

$ns at $val(stop) "$node_($i) reset";

}

# ending nam and the simulation

$ns at $val(stop) "$ns nam-end-wireless $val(stop)"

$ns at $val(stop) "stop"

$ns at 150.01 "puts \"end simulation\" ; $ns halt"

proc stop {} {

global ns tracefd namtrace

$ns flush-trace

close $tracefd

close $namtrace

}

$ns run

CHAPTER 6

CONCLUSION

The beacon updates policy employed in geographic routing protocols to the node mobility dynamics and the traffic load. The Adaptive Position Update (APU) employs two mutually exclusive rules. The Mobility Prediction (MP) rule uses mobility prediction to estimate the accuracy of the location estimate and adapts the beacon update interval, instead of using periodic beaconing. The On Demand Learning (ODL) rule allows nodes along the data forwarding path to maintain an accuracy of the local topology by exchanging beacons in response to data packets that are overheard from new neighbors. The analyzation of the beacon overhead and local topology accuracy of APU and validated the analytical model with the simulation results. Embedding APU using NS-2 simulations for varying node speeds and traffic load. The results indicate that the APU generates less or similar amount of beacon overhead as other beaconing schemes but achieve better packet delivery ratio, average end-to-end delay and energy consumption.

5.3 SCREENSHOTS:

Figure 5.3.1 Creation of Nodes

Figure 5.3.2 Source and Destination

Periodic Beaconing For Geographic Routing Computer Science Essay

You may also find these documents helpful