24-12-2012, 02:57 PM
Project on Mobile Ad-hoc Networking and Clustering
[attachment=45127]
Introduction
A mobile ad-hoc network, or MANET, consists of identical nodes that travel around freely
and independently and communicate wirelessly. The obvious problem in ad-hoc networking is
how to transfer messages between two nodes that are not in range to communicate directly.
Ad-hoc is a very hot topic at the moment and is already expanding greatly in use. It has a lot
of applications and many good reasons for its popularity. Ad-hoc networks are easy to deploy
and quickly self organized. It is decentralized and independent on infrastructure. Presented in
this rapport are a few of the many different routing protocols and clustering algorithms.
History
In the late 1960s the Air Force Office of Scientific Research started to do some research on the
subject of using radio for a packet switched network communication. In the early 1970s DARPA
provided continued funding for this research at the University of Hawaii. The project was called
ALOHA (Areal Locations of Hazardous Atmospheres) and here not only were new ideas of mobile
packet radio born but also the basis of Ethernet was developed. In 1977 there was a big
demonstration of the Packet Radio net, SATNET, and the ARPANET where messages were sent
across the US.
In 1983 another DARPA funded project called SURAN (Survivable Radio Network) started. In this
project the goals were to:
* develop a small, low-cost, low-power radio that would support more sophisticated packet radio
protocols than the DARPA Packet Radio project from the 1970s
* develop and demonstrate algorithms that could scale to tens of thousands of nodes
* develop and demonstrate techniques for robust and survivable packet networking in sophisticated
electronic attacks
There were several follow-up projects funded by DARPA projects. Two examples of there are Lowcost
Packet Radio (LPR) and GloMo.
Applications/Uses
The original applications of ad-hoc networks were of a military kind. Vehicles on a battlefield are
certainly mobile and move around in unpredicable manners. This is the original scene from where the
very idea of ad-hoc networking was born. Other applications are in rescue opperations where ad-hoc
networks could be used by both police and firefighters. Search and rescue missions are also suitible
applications. Possible commercial purposes could be for taxi communication, on boast, aircrafts and in
sports stadiums. Personal uses are for laptops and notebook computers. Ad-hoc networking has even
reached the entertainmentbusiness with sonys playstation portable which uses this for multiplayer
gaming.
Routing
The obvious problem with ad-hoc networking is how to send a message from one node to another with
no direct link. This is the problem of routing. Because the nodes in the network are moving around
unpredictibly, which nodes that are directly linked together are changing all the time. This means that
the topology of an ad-hoc network is constantly changing and this is what makes routing so difficult.
There are two main approaches to this problem. There are also combinations of the two. The first
approach is a pro-active approach which is table driven and uses periodic protocols. This means that
all nodes have tables with routing information which are updated at intervals. The second approach is
re-active, source-initiated or on-demand. This means that every time a message is sent it first has to There are many different protocols that are in accordance with the two different routing approaches.
Different protocols are specialized in different aspects of the routing.
CGSR (Clusterhead Gateway Switch Routing)
In CGSR [2] the ad-hoc network is divided into clusters. Every cluster contains a node that is given the
role of being a clusterhead and nodes that have direct links to two or more clusterheads are gateways.
Routing is then done through the clusterheads using the same method as in DSDV. Dividing up the
network into clusters can be done in many ways (more on this later) but the most important thing is
that the clusterhead roles should not be changed too frequently. This leads to an unnecessary amount
of communication for just organizing the network.
To deal with this problem the LCC (Least Cluster Change) algorithm is therefore used. What this
algorithm does is that the clusterhead election is only performed at two occasions. The first occasion
is when two clusterheads get so close together that they can communicate directly. The second is
when a node loses contact with a clusterhead.
Every node has two tables. One table contains the information of which clusterhead every node in the
network belongs to. The other table is a distance-vector-routing table with the information of the next
hop node for all clusterheads.
When a message is to be delivered from node 1 to node 12 in the example below, routing is done by
the following steps. First the clusterhead of node 12 is looked up in the cluster member table to find
node 11. Second the next hop node for clusterhead-node 11 is looked up in the distance-vector table
to find node 2. The message is then sent to node 2 which passes it on to its gateway-node leading to
clusterhead-node 11. It is them passed on between gateways and clusterheads until it reaches node
11. Node 11 then passes is on to the destination node 12.
WRP (Wireless Routing Protocol)
A problem of the Bellman-Ford protocol is the count-to-infinity problem. This is a problem that is
solved by WRP [3]. When the link between a node and its only neighbour is broken it loses contact
with the network. In the example below node A loses contact with node B. When B realizes that it has
lost direct contact with A it looks for other paths. When B receives the table information of C it sees
that, C has a link to A by 2 hops. B updates its table by adding one hop for the distance to A, and sets
the next hop to be C. When C receives B updated table, it notices that the distance from B to A has
increased. Since the entry for next hop node going to A is B, the entry for the hop distance to A has to
be changed to what B has plus one. As tables are updated no one will realize that they have lost
contact with A but the distance to A will count up to infinity.
DSR (Dynamic Source Routing)
In DSR [5] all nodes keep a route cache which holds routing information of other nodes. Entries in the
routing cache hold the entire routing information of a route, not just the next hop node. If a node is not
in the routing cache that a source node wants to communicate with, the source node broadcasts a
route request, much like in AODV. This route request holds the information of source and destination
but also the nodes on the path, called a route record. When an intermediate node receives a route
request, it checks if it is in this route record. If it is, the message is discarded; otherwise it adds itself to
the route record and sends the route request on to its neighbours.
SSR (Signal Stability Routing)
SSR [8] similarly to ABR also introduce new ideas of how to measure which is the best route. SSR
uses the measure of signal strength of a link. A link with a strong signal reduces the risk of packet loss
and also indicates that the two nodes are relatively close. If two nodes are close the time for them to
be separated is greater, thus the chance that the link is going to stay up longer is greater too.
Summery of Table-Driven Protocols
Because in DSDV every node holds information of routing to everyone and this information is updated
at intervals, it has problems with a large amount of overhead wish grows as O(n2). In CGSR routing is
limited to the clusterheads. This allows for more nodes than in DSDV but there is still a lot of data
maintained in the two tables that every node holds. Also routing is dependant on clusterheads, making
the organization less distributed. This causes a lot of resources to be consumed when running the
clustering algorithm.
In WRP every node has four tables to avoid the temporary routing loops that the other table-driven
protocols have problem with. However the time to repair a route due to a broken link is much lower in
WRP since it only notifies the neighbouring nodes about the changes.
Summery of Source-Initiated On-Demand Protocols
The overhead of DSR is greater than that of AODV because the packages contain the whole route
information where as in AODV only the next hop node is considered. The memory overhead is also
larger because of the same argument. An advantage of DSR however is that it doesn’t send periodic
routing messages. This means that power is saved and the utilization of the bandwidth is better. DSR
can hold several route cache entries for the same destination. This is the fastest way of solving the
problem with a broken link, since no repair procedure has to be invoked.
Both AODV and TORA can support multicast. The main advantage of TORA is, like DSR, its support
for multiple routes. The main drawback of TORA is that it demands the nodes to have synchronized
clocks. So if the nodes don’t have GPS or some other way of synchronizing clocks TORA cannot be
used. Also if the synchronization fails the algorithm fails.
ABR doesn’t always chose the route with the least hops, but the most stable route. This means that
the route will be more long-lived, thus fewer route reconstructions have to be made. Another
advantage of ABR, in contrast to all other protocols, is that it avoids duplicate packages. The
drawback on the other hand is the power consumption of the frequent beaconing messages.
[attachment=45127]
Introduction
A mobile ad-hoc network, or MANET, consists of identical nodes that travel around freely
and independently and communicate wirelessly. The obvious problem in ad-hoc networking is
how to transfer messages between two nodes that are not in range to communicate directly.
Ad-hoc is a very hot topic at the moment and is already expanding greatly in use. It has a lot
of applications and many good reasons for its popularity. Ad-hoc networks are easy to deploy
and quickly self organized. It is decentralized and independent on infrastructure. Presented in
this rapport are a few of the many different routing protocols and clustering algorithms.
History
In the late 1960s the Air Force Office of Scientific Research started to do some research on the
subject of using radio for a packet switched network communication. In the early 1970s DARPA
provided continued funding for this research at the University of Hawaii. The project was called
ALOHA (Areal Locations of Hazardous Atmospheres) and here not only were new ideas of mobile
packet radio born but also the basis of Ethernet was developed. In 1977 there was a big
demonstration of the Packet Radio net, SATNET, and the ARPANET where messages were sent
across the US.
In 1983 another DARPA funded project called SURAN (Survivable Radio Network) started. In this
project the goals were to:
* develop a small, low-cost, low-power radio that would support more sophisticated packet radio
protocols than the DARPA Packet Radio project from the 1970s
* develop and demonstrate algorithms that could scale to tens of thousands of nodes
* develop and demonstrate techniques for robust and survivable packet networking in sophisticated
electronic attacks
There were several follow-up projects funded by DARPA projects. Two examples of there are Lowcost
Packet Radio (LPR) and GloMo.
Applications/Uses
The original applications of ad-hoc networks were of a military kind. Vehicles on a battlefield are
certainly mobile and move around in unpredicable manners. This is the original scene from where the
very idea of ad-hoc networking was born. Other applications are in rescue opperations where ad-hoc
networks could be used by both police and firefighters. Search and rescue missions are also suitible
applications. Possible commercial purposes could be for taxi communication, on boast, aircrafts and in
sports stadiums. Personal uses are for laptops and notebook computers. Ad-hoc networking has even
reached the entertainmentbusiness with sonys playstation portable which uses this for multiplayer
gaming.
Routing
The obvious problem with ad-hoc networking is how to send a message from one node to another with
no direct link. This is the problem of routing. Because the nodes in the network are moving around
unpredictibly, which nodes that are directly linked together are changing all the time. This means that
the topology of an ad-hoc network is constantly changing and this is what makes routing so difficult.
There are two main approaches to this problem. There are also combinations of the two. The first
approach is a pro-active approach which is table driven and uses periodic protocols. This means that
all nodes have tables with routing information which are updated at intervals. The second approach is
re-active, source-initiated or on-demand. This means that every time a message is sent it first has to There are many different protocols that are in accordance with the two different routing approaches.
Different protocols are specialized in different aspects of the routing.
CGSR (Clusterhead Gateway Switch Routing)
In CGSR [2] the ad-hoc network is divided into clusters. Every cluster contains a node that is given the
role of being a clusterhead and nodes that have direct links to two or more clusterheads are gateways.
Routing is then done through the clusterheads using the same method as in DSDV. Dividing up the
network into clusters can be done in many ways (more on this later) but the most important thing is
that the clusterhead roles should not be changed too frequently. This leads to an unnecessary amount
of communication for just organizing the network.
To deal with this problem the LCC (Least Cluster Change) algorithm is therefore used. What this
algorithm does is that the clusterhead election is only performed at two occasions. The first occasion
is when two clusterheads get so close together that they can communicate directly. The second is
when a node loses contact with a clusterhead.
Every node has two tables. One table contains the information of which clusterhead every node in the
network belongs to. The other table is a distance-vector-routing table with the information of the next
hop node for all clusterheads.
When a message is to be delivered from node 1 to node 12 in the example below, routing is done by
the following steps. First the clusterhead of node 12 is looked up in the cluster member table to find
node 11. Second the next hop node for clusterhead-node 11 is looked up in the distance-vector table
to find node 2. The message is then sent to node 2 which passes it on to its gateway-node leading to
clusterhead-node 11. It is them passed on between gateways and clusterheads until it reaches node
11. Node 11 then passes is on to the destination node 12.
WRP (Wireless Routing Protocol)
A problem of the Bellman-Ford protocol is the count-to-infinity problem. This is a problem that is
solved by WRP [3]. When the link between a node and its only neighbour is broken it loses contact
with the network. In the example below node A loses contact with node B. When B realizes that it has
lost direct contact with A it looks for other paths. When B receives the table information of C it sees
that, C has a link to A by 2 hops. B updates its table by adding one hop for the distance to A, and sets
the next hop to be C. When C receives B updated table, it notices that the distance from B to A has
increased. Since the entry for next hop node going to A is B, the entry for the hop distance to A has to
be changed to what B has plus one. As tables are updated no one will realize that they have lost
contact with A but the distance to A will count up to infinity.
DSR (Dynamic Source Routing)
In DSR [5] all nodes keep a route cache which holds routing information of other nodes. Entries in the
routing cache hold the entire routing information of a route, not just the next hop node. If a node is not
in the routing cache that a source node wants to communicate with, the source node broadcasts a
route request, much like in AODV. This route request holds the information of source and destination
but also the nodes on the path, called a route record. When an intermediate node receives a route
request, it checks if it is in this route record. If it is, the message is discarded; otherwise it adds itself to
the route record and sends the route request on to its neighbours.
SSR (Signal Stability Routing)
SSR [8] similarly to ABR also introduce new ideas of how to measure which is the best route. SSR
uses the measure of signal strength of a link. A link with a strong signal reduces the risk of packet loss
and also indicates that the two nodes are relatively close. If two nodes are close the time for them to
be separated is greater, thus the chance that the link is going to stay up longer is greater too.
Summery of Table-Driven Protocols
Because in DSDV every node holds information of routing to everyone and this information is updated
at intervals, it has problems with a large amount of overhead wish grows as O(n2). In CGSR routing is
limited to the clusterheads. This allows for more nodes than in DSDV but there is still a lot of data
maintained in the two tables that every node holds. Also routing is dependant on clusterheads, making
the organization less distributed. This causes a lot of resources to be consumed when running the
clustering algorithm.
In WRP every node has four tables to avoid the temporary routing loops that the other table-driven
protocols have problem with. However the time to repair a route due to a broken link is much lower in
WRP since it only notifies the neighbouring nodes about the changes.
Summery of Source-Initiated On-Demand Protocols
The overhead of DSR is greater than that of AODV because the packages contain the whole route
information where as in AODV only the next hop node is considered. The memory overhead is also
larger because of the same argument. An advantage of DSR however is that it doesn’t send periodic
routing messages. This means that power is saved and the utilization of the bandwidth is better. DSR
can hold several route cache entries for the same destination. This is the fastest way of solving the
problem with a broken link, since no repair procedure has to be invoked.
Both AODV and TORA can support multicast. The main advantage of TORA is, like DSR, its support
for multiple routes. The main drawback of TORA is that it demands the nodes to have synchronized
clocks. So if the nodes don’t have GPS or some other way of synchronizing clocks TORA cannot be
used. Also if the synchronization fails the algorithm fails.
ABR doesn’t always chose the route with the least hops, but the most stable route. This means that
the route will be more long-lived, thus fewer route reconstructions have to be made. Another
advantage of ABR, in contrast to all other protocols, is that it avoids duplicate packages. The
drawback on the other hand is the power consumption of the frequent beaconing messages.