If we review what we have covered in the first part , we outlined
- what mobile adhoc network technology is,
- in which fields this technology is being used
- what are the requirements for adhoc routing ?
- what are the routing protocols ? AODV (one of the most preferred routing protocols)
We will continue talking about routing protocols. The outline of this post as follows ;
1) Selected Routing Protocols
- Dynamic Source Routing (DSR)
- Location Aided Routing (LAR)
- Optimized Link State Routing (OLSR)
2) Routing Dependability in Ad hoc Networks
3) Performance Evaluation of Ad hoc Networks
Let's start with what we have as Routing Protocol except AODV .
1) Selected Routing Protocols
Dynamic Source Routing (DSR)
- Very similar to AODV- It is a reactive protocol (on demand)
- No proactive mechanisms.
- When I want to send a packet to destination , I find a route. ( I do not know where the destination is, flooding happens like in AODV)
A different thing with DSR is, each node appends its own identifier when forwarding RREQ (Request message) . Therefore RREQ grows in each hope.
In this figure, S wants to send a package to D but does not know the route. Therefore, it start flooding the message. First it sends it to its neighbours (B,C,E) , then it goes on like that. C sends the message to H,G ; and B sends it to A,H (For instance in this case, H receives packet RREQ from two neighbors which might mean a potential collision). However we do not care about collision, because the network is dense and I just would like to reach collision, even if there happens a collision most probably another node will send the message to H again, maybe A and I nodes in this case.
As you can see in the figure, each node that receives the packet adds its own identity into the message.
When message packet reaches D, D knows that it is for him and stops broadcasting it. And then RREP is sent by D from the reverse path. ( Rout reply can be sent by reversing the route in Route Request (RREQ) only if links are guaranteed to be bi-directional. IF unidirectional (asymmetric) links are allowed which means that "Ok, D knows that S sent the message from the path S->E->F->J->D, what happens if link from F to J (F->J) is asymmetric meaning that there is no way back from J to F in which case reverse path cannot be used " * . That's why, another route discovery from S to D is handled to find a path of which reverse path can be used in order to send the reply back . This happens of course if D does not have a route back to S.
* It might happen when message is delivered to the destination but later on a link back is broken ( maybe destination is out of the range ) .
Some extra mechanisms like we use in AODV can be used in order to limit broadcast in case of a re ally big network.
You might see the obvious difference between AODV and DSR from this graph above. We do not deal with tables as we do in AODV ( you need to update tables and etc) . Here, we just need to reverse the path back to the source.
After destination receives the message, it uses the path recorded in RREQ and finds out the reverse path. There is no need to store any information in the intermediary node as we do in AODV such as having tables. Briefly the nodes between do nothing and know nothing about the route because their task it to only send the package to their neighbours. Remember ! We are only trying to find the ROUTE ! We have not sent the real packet yet. The "message" we were quoting was about RREQ message. Do not confuse with RREQ message and payload (real message) .
After finding the route ;
The information about route is stored in only S and D.
As you can see, source specifies the route. But here is the thing about DSR. Ok route is known, but when S sends DATA to E, E will add its own information into the DATA Message packet header, right ? Imagine this is repeated each time the data is given to the next node. Instead of DATA[S,E,F,J,D] we will come up with IP addresses and stuff.
This will definitely cause overhead.
That's all what we need to know about DSR :) .
To recap , we have no tables unlike AODV. There might be some overhead as the route grows.
We have talked about Reactive Protocols (AODV and DSR) , now it is time to cover some Proactive Protocols.
* Location information may be obtained using GPS.
LAR defines an expected zone. I know some information about the topology, I have some idea where destination could be. By this way, I can calculate the zone so that I do not need to waste my source by flooding message over the whole network.
Expected region is calculated based on potentially old location information and knowledge of the destination's speed.
There is also another term request zone which means a zone in that source and destination nodes exist.
Let's have a look at this graph below.
As you can imagine, when S wants to send a message to D, the nodes that will spread the message through D are restricted in the Request Zone. If a node out of the request zone such as A receives the message, it checks its zone and sees that he is not in the zone so that he will not flood that message any longer.
However it could be more efficient if some nodes inform Source about estimated request zone in more accurate manner, right ? Some nodes might have more recent information and it would be better if we could make use of those information.
This newly found, discovered request zone by the help of other nodes within the zone is called "Adaptive request zone".
* Reduces overhead of route discovery
* Another thing is that there is no way of overcoming a situation like shown below.
Let's assume that blue zone is our request zone and there is our destination in the corner of that zone (blue square) . However there is a barrier (obstacle) in front of that node depicted as red lines that does not let us reach our destination. Only solution seems to go other way around the red line which is not possible because it is out of our request node. Therefore in such cases, we might end up with some dead end.
Optimized Link State Routing (OLSR)
We are able to limit flooding without physical location as mentined briefly before. If we have a known route, we might take it as a reference and create a rule from that for new discovery. We might state that route requests are propagated only along paths that are close to the previously known route.
Closeness property defined without using physical location.
OLSR is designed for different types of networks.
How does it work ?
Link state routing is proactive. It has all information before we need them. And local information is disseminated network wide. You are basically monitoring everything.
It is actually very similar to Standard Internet Routing. Therefore there is overhead, and the question is it really applicable for adhoc networks ?
There must be some optimizations. So, I will broadcast my local information to whole network, right. But while I do it in OLSR, it applies an optimized version of flooding which aims to broadcast a message only to selected neighbours. It is called multipoint relays (MPR) . MPR is the key feature of OLSR.
How does MPR work ?
MPR selection : We can add some info into Hello messages, and we can calculate 2 hops neighbors.
Link State Messages : If we have an updated link information about something, and if others need to know it we just relay this information.
However in OLSR, I select two or three multipoint relays and can reach all of my neighbors. Briefly for Large and Dense network networks it is feasible and makes sense to use OLSR .
Moreover, OLSR has low latency. Because we have a routing table. When I want to send a packet, I check my table and just send it. Compared to that, AODV has to discover route when needed , reply back and stuff. OLSR has that information on hand.
Recall that in ad hoc networks, there is mobility, dynamic situations.
In this part, our concern is Routing system.
Routing protocols need to find out whom to communicate , which path to choose.
How can we characterize routing system shown as a box in the graph above ? This is what we will outline now.
We also need to define what Routing Dependability is. It is trustworthiness of a routing system.
Well-behaving nodes : that works, forwards the packet.
Malicious nodes : the ones that inject false information into messages or remove them completely from the network ( black holes) .
It has been proven that if the number of selfish nodes increases, the packet loss in the network increases linearly as well.
Besides that, in case of AODV, if there are many selfish nodes in the network we need to incerase the number of control messages ( to keep the track of what is going on in the network , and reestablish route if a node does not forward the packet ) . It results in increase of routing overhead.
Selfish nodes: the ones that receives the packet but do not forward it .
How to measure dependability ?
There are many metrics for this purpose such as sent packets (bytes) , Lost packets (Bytes) , mean end to end delay , mean path length, maximum path length, total # of RREQ, RREP, RERR . The metrics you would select are totally up to what routing protocol you choose.
- Induced by mobility : High topology dynamics
- Induced by wireless communication
- Induced by node misbehavior ( we might want to add some extra mechanisms to overcome this)
You need to know what you want to characterize in your system. You need to have a proper goal first. There is no such thing as general model.
Goals -> correct metrics, workloads, methodology.
Your performance evaluation should represent the actual usage of the system.
Challenge : Qualify and quantify the effects of
node misbehavior on the overall performance of the routing system.
We would like to see how the system behaves.
What about choice of evaluation technique ?
- Real world observations are not possible because there is no large scale MANET, and it would be expensive to set up a new one.
- Emulation / Testbed experiments are possible but in a small scale.
- Simulation studies are being conducted.
Compared to real world observations, we can play with the settings of input and output values in emulation, simulation experiments. I can define input, predict output. Workload would be input and calculations could be output.
Below you can see the result of an experiment.
It is for sure that there are many issues need to be handled if an optimized ad hoc network needs to be implemented which does not seem possible with today's technology.
For instance what if after 2 hops away the speed is decreasing while it is pretty fast in the nodes close to the source ? Should I buffer it ? or what ? I need some flow control mechanisms to deal with these kind of problems. Another problem would be priority ? which packet is important , my packet or neighbours' ? A lot of research is being done on these issues.
What about security ? What if there is DoS attacks ? Some malicious nodes can use a specific node just to kill its battery. How can we overcome it ? or malicious nodes can temper messages , who can prevent it and how ?
Smart antennas might change the future of ad hoc networks.
Self organizing, mobile and wireless nodes
Absence of infrastructure, multi-hop routing necessary
System are both terminals ( end systems ) and routers (nodes)
Routing is a main problem in ad hoc networks
Resources : The content of this post has been generated from the slides of the presentation that was given by Matthias Hollick in UIO in 2007.
Some extra mechanisms like we use in AODV can be used in order to limit broadcast in case of a re ally big network.
You might see the obvious difference between AODV and DSR from this graph above. We do not deal with tables as we do in AODV ( you need to update tables and etc) . Here, we just need to reverse the path back to the source.
After destination receives the message, it uses the path recorded in RREQ and finds out the reverse path. There is no need to store any information in the intermediary node as we do in AODV such as having tables. Briefly the nodes between do nothing and know nothing about the route because their task it to only send the package to their neighbours. Remember ! We are only trying to find the ROUTE ! We have not sent the real packet yet. The "message" we were quoting was about RREQ message. Do not confuse with RREQ message and payload (real message) .
After finding the route ;
The information about route is stored in only S and D.
This will definitely cause overhead.
That's all what we need to know about DSR :) .
To recap , we have no tables unlike AODV. There might be some overhead as the route grows.
We have talked about Reactive Protocols (AODV and DSR) , now it is time to cover some Proactive Protocols.
Location Aided Routing (LAR)
LAR is more detailed than AODV and DSR in this manner. It is actually designed as an extension of DSR. It has some extra features. As its name states, it gives information about location of the nodes. By this way, broadcasting can be limited.* Location information may be obtained using GPS.
LAR defines an expected zone. I know some information about the topology, I have some idea where destination could be. By this way, I can calculate the zone so that I do not need to waste my source by flooding message over the whole network.
Expected region is calculated based on potentially old location information and knowledge of the destination's speed.
There is also another term request zone which means a zone in that source and destination nodes exist.
Let's have a look at this graph below.
As you can imagine, when S wants to send a message to D, the nodes that will spread the message through D are restricted in the Request Zone. If a node out of the request zone such as A receives the message, it checks its zone and sees that he is not in the zone so that he will not flood that message any longer.
NOTE ! Each node has to know its physical location to determine whether it is within the request zone or not.
On condition that route is not found in the request zone due to miscalculation of request zone (destination node might move faster than expected) , we can always extend the request zone .However it could be more efficient if some nodes inform Source about estimated request zone in more accurate manner, right ? Some nodes might have more recent information and it would be better if we could make use of those information.
This newly found, discovered request zone by the help of other nodes within the zone is called "Adaptive request zone".
! Recall that LAR is like an extension of DSR. In LAR we are keeping the track of the location of each node + we also have route information as DSR has. We can make use of route information in such a way that next discovery can be based on this previously determined route. For instance, we might limit the broadcast or flooding by stating that new route should include at lease two-three nodes of the old one.
Advantages of LAR
* Reduces the scope of route request flood* Reduces overhead of route discovery
Disadvantages of LAR
* We need more information (location of nodes)* Another thing is that there is no way of overcoming a situation like shown below.
Let's assume that blue zone is our request zone and there is our destination in the corner of that zone (blue square) . However there is a barrier (obstacle) in front of that node depicted as red lines that does not let us reach our destination. Only solution seems to go other way around the red line which is not possible because it is out of our request node. Therefore in such cases, we might end up with some dead end.
Optimization for LAR
Optimized Link State Routing (OLSR)
We are able to limit flooding without physical location as mentined briefly before. If we have a known route, we might take it as a reference and create a rule from that for new discovery. We might state that route requests are propagated only along paths that are close to the previously known route.
Closeness property defined without using physical location.
Optimized Link State Routing (OLSR)
The name of the protocol says much about its functionality. So far, we had protocols that are reactive, not updating routing information all the time because it is costly and network is so dynamic and so on.OLSR is designed for different types of networks.
How does it work ?
- It floods status of its links
- Re-broadcasts link state information received from its neighbor.
- Keeps track of link state information received from other neighbors.
- Uses these information to determine next hop to destinations.
Link state routing is proactive. It has all information before we need them. And local information is disseminated network wide. You are basically monitoring everything.
It is actually very similar to Standard Internet Routing. Therefore there is overhead, and the question is it really applicable for adhoc networks ?
There must be some optimizations. So, I will broadcast my local information to whole network, right. But while I do it in OLSR, it applies an optimized version of flooding which aims to broadcast a message only to selected neighbours. It is called multipoint relays (MPR) . MPR is the key feature of OLSR.
How does MPR work ?
A node is selected with two rules ;
1) Any 2-hop neighbor must be covered by at least one multipoint relay. In our example above, A's multipoint relays are node C and E in order to reach G and H.
2) The number of multipoint relays should be minimized (per node)
2) The number of multipoint relays should be minimized (per node)
Core features of OLSR
Link sensing : By sending Hello messages to the neighbors, we can learn about our neighbourhood.MPR selection : We can add some info into Hello messages, and we can calculate 2 hops neighbors.
Link State Messages : If we have an updated link information about something, and if others need to know it we just relay this information.
Conclusion for OLSR
Ok so, it seems a bit complicated, a lot of overhead. But it is well suited for some networks ( Large, Dense networks ) . Because, If have many neighbours and prefer to use AODV, I have to send them all my messages which means a lot of overhead.However in OLSR, I select two or three multipoint relays and can reach all of my neighbors. Briefly for Large and Dense network networks it is feasible and makes sense to use OLSR .
Moreover, OLSR has low latency. Because we have a routing table. When I want to send a packet, I check my table and just send it. Compared to that, AODV has to discover route when needed , reply back and stuff. OLSR has that information on hand.
2) Routing Dependability in Ad hoc Networks
- The effects of node misbehavior.
- Modelling adhoc networks.
Recall that in ad hoc networks, there is mobility, dynamic situations.
In this part, our concern is Routing system.
How can we characterize routing system shown as a box in the graph above ? This is what we will outline now.
We also need to define what Routing Dependability is. It is trustworthiness of a routing system.
Node Misbehavior
A node in the middle may keep the message and not forward to package. It can affect the overall performance of the system. There are three different nodes.Well-behaving nodes : that works, forwards the packet.
Malicious nodes : the ones that inject false information into messages or remove them completely from the network ( black holes) .
It has been proven that if the number of selfish nodes increases, the packet loss in the network increases linearly as well.
Besides that, in case of AODV, if there are many selfish nodes in the network we need to incerase the number of control messages ( to keep the track of what is going on in the network , and reestablish route if a node does not forward the packet ) . It results in increase of routing overhead.
Selfish nodes: the ones that receives the packet but do not forward it .
How to measure dependability ?
There are many metrics for this purpose such as sent packets (bytes) , Lost packets (Bytes) , mean end to end delay , mean path length, maximum path length, total # of RREQ, RREP, RERR . The metrics you would select are totally up to what routing protocol you choose.
Routing Dependability Problems
- Most ad hoc routing algorithms assume only well-behaving nodes to support multi-hop operation of the network. However if something goes wrong in between, everything can be affected in a negative way.
- Induced by mobility : High topology dynamics
- Induced by wireless communication
- Induced by node misbehavior ( we might want to add some extra mechanisms to overcome this)
3) Performance Evaluation of Ad hoc Networks
Basic Terms- Performance Analysis = Analysis + Computer Systems
- System = any collection of hardware + software
- Metrics = the criteria used to evaluate the system performance
- Workloads = the requests made by the users of the system
You need to know what you want to characterize in your system. You need to have a proper goal first. There is no such thing as general model.
Goals -> correct metrics, workloads, methodology.
Your performance evaluation should represent the actual usage of the system.
How to analyze (Mobile Ad hoc ) networks ?
Challenge : Qualify and quantify the effects of
node misbehavior on the overall performance of the routing system.
We would like to see how the system behaves.
What about choice of evaluation technique ?
- Real world observations are not possible because there is no large scale MANET, and it would be expensive to set up a new one.
- Emulation / Testbed experiments are possible but in a small scale.
- Simulation studies are being conducted.
Compared to real world observations, we can play with the settings of input and output values in emulation, simulation experiments. I can define input, predict output. Workload would be input and calculations could be output.
Below you can see the result of an experiment.
Challenges in Ad hoc Networks
- Security,
- QoS,
- Scalability,
- Heterogeneity,
- Adaptation,
- Dependability.
It is for sure that there are many issues need to be handled if an optimized ad hoc network needs to be implemented which does not seem possible with today's technology.
For instance what if after 2 hops away the speed is decreasing while it is pretty fast in the nodes close to the source ? Should I buffer it ? or what ? I need some flow control mechanisms to deal with these kind of problems. Another problem would be priority ? which packet is important , my packet or neighbours' ? A lot of research is being done on these issues.
What about security ? What if there is DoS attacks ? Some malicious nodes can use a specific node just to kill its battery. How can we overcome it ? or malicious nodes can temper messages , who can prevent it and how ?
Smart antennas might change the future of ad hoc networks.
Summary
MANET :Self organizing, mobile and wireless nodes
Absence of infrastructure, multi-hop routing necessary
System are both terminals ( end systems ) and routers (nodes)
Routing is a main problem in ad hoc networks
- Topology based, destination based, hierarchical, geographical, cluster-based, etc. strategies,
- Proactive, reactive, hybrid, etc. protocols.
- Problems persist: QoS, Security, Scalability, Heterogeneity, ...
Resources : The content of this post has been generated from the slides of the presentation that was given by Matthias Hollick in UIO in 2007.
No comments:
Post a Comment