In recent decade, the usage as well as popularity of mobile communication has widely increased all around the world. So the devices are becoming more and more compact, the standby time of the batteries are being improved for a longer period and communication protocols are getting more strong and providing more sturdy throughput. Now days, Wireless Technology has taken over the Wire Communication, thus giving the facility of mobility to the users.
As we know that the wireless networks are used for the communication between two systems or to transfer the information from one computer to another computer. This is usually done by the help of central base station called, “Access Point”. The main idea of mobile ad-hoc networking is, Instead of using “Access Point” computers can communicate with each other in peer-to peer mode which can dramatically increase the distance of the wireless network, this is done by adding the routing functionalities into a mobile node.
- Implementation Work:
In my thesis, modification of Protocol is been discussed which is already been used in mobile wireless networks. Now, it is applied to follow the RFC to describe the protocol and to be as more extended as it can be.
In the thesis the Optimized Link State Routing Protocol is implemented and the extension on the routing protocol is also the part of my thesis.
1.2 Chapter overview:
Chapter 1 is the general Introduction and in Chapter 2, I have given the introduction to Mobile Ad-hoc Networks some basics of wireless data-communication are also introduced in it. I have also included the two routing protocol that are proposed by (IETF). Chapter 3 is for the Core-Functionality of the OLSR. The process of implementing and simulations of OLSR protocol is described in chapter 4. Our proposed model and its extension to OLSR are presented in chapter 5.
MOBILE AD-HOC NETWORKS
The basis on which much of the Wireless Technology works, is known as “Point to Point Communication”. Popular solutions like Global System for Mobile communication (GSM) and Wireless Local Area Network (WLAN), use the same approach, in which ‘mobile node' is used that communicates with centralized Access point. Centralization for configuration and operation is required for these types of networks. Multi-Hop approach is opposite to the model that is mentioned above. In Multi-hop if the end point is out of direction, the nodes can communicate with each other by utilizing the other node as relays of traffic. Multiple nodes are may be involved between the communications of two nodes. Sometimes it happens that a node is not been accessed directly. Data or control packets can be sent from one node to another node through several nodes. These types of networks are called mobile ad hoc networks.
The multi-hop model is used by MANET. MANETs are infrastructure less where one node can communicate with another node through wireless media. Node mobility is freely allowed as there is no structured media, which translates into a constantly changing network topology. MANETs can also provide networking connectivity on rough scenarios like “disaster relief areas, battle fields” etc, and considered as best alternative where environmental conditions are another factor that changes the network topology. Using the location of nodes and the availability of direct communication between each pair of nodes the network topology is described.
2.1 Ad-hoc networks:
GSM is one of the centralized networks which cannot be used in all situations. Instead of GSM we can use ad-hoc networks in those scenarios like; student uses the laptop to participate in the lecture, emergency disaster relief personnel coordinating efforts in natural disaster and military attacks etc. MANETs has several set of diverse applications which range from ‘small static networks restrained by power sources, to large mobile networks which are highly dynamic'.
In Order to allow multi-hop communication every node in the network should be capable to act as routers for each other, (See Figure 2-1). Nodes support one another for communicating and hence they create a virtual set of connections. The existence and operation of the Ad hoc network is only possible if the nodes show a cooperative behavior.
Routing protocol sets up and maintains the Routes. Routing protocols create and maintain the virtual set of connections.
- Hassene Bouhouch, Sihem Guemara EL Fatmi, “QoS In Ad Hoc Networks by Integreting Activity in the OLSR.
- Leila Boukhalfa, Pascale Minet and Serge Midonnet, “QoS support in a MANET based on OLSR and CBQ.
There are many different types of routing protocols for ad hoc networks which are categorized as follows;
The difference between the reactive and proactive protocol is that in reactive protocol the routes are discovered when they are needed and in proactive protocol the route are established in advance before there usage.
2.1.1 Wireless communication
We have seen that the use of wireless networking is increasing day by day both in mobile and fixed scenarios. Whereas now the wireless network can provide the High Quality Multimedia services and the Wireless Local Area Network (WLAN) now provides up-to 54 Mbps to both residential and business environments with high quality of service QoS. MANETs are the new paradigm of wireless wearable devices that enables person to person, person to machine and machine to machine communication.
IEEE 802.11 does not support multi-hop communication by it self. Two modes are defined for communication using WLAN devices:
- Infrastructure mode: In the wireless network we there are different nodes and a central point called Access point. All the nodes communicate whit each other via Access point such configuration is known as Basic Service Set (BSS). A set of two or more BSSs forms an Extended Service Set (ESS).
- Ad hoc mode: This is a peer-to-peer mode. This configuration is called Independent Basic Service Set (IBSS), and is useful for establishing a network where nodes must be able to communicate directly and without any centralized access point.
While setting up a MANET, the mode to be used most certainly is The Ad-hoc mode, but one of the most basic requirements is missing here which is ‘Multi hop'. The Ad Hoc mode enables Traffic to be transmitted to the adjacent nodes only within the radio range, therefore there is a need for MANET routing protocols to set up and maintain traffic paths.
2.1.2 Traditional IP routing:
For the selection of the destination network of the packet, IP works with the ARP by checking the IP address and the subnet mask. TCP/IP host uses the Routing tables to maintain the knowledge of other networks and hosts. Routing tables are used when a host wants to forward the packet, then the packet is forwarded on the route that shows the best match for the destination, but if its finds no network match is selects the default route.
All the hosts on the same network or on the same subnet can communicate with each other directly, but to be able to communicate with other networks gateways are used between the two networks. This means that in a single one-hop network all the hosts those are on the same subnet are available.
The case is entirely different when working on wireless multi-hop networks. So the idea of nodes being available “on the link” must be redefined. In MANETs nodes routes traffic by retransmitting packets on the interface they arrived.
When it comes to routing, different frame of mind is required in MANET. MANETs do not use aggregation, all routing is host based. This means that a sender has a specific route for all destinations within the MANET and in a wired network all nodes in the local network are considered available on the link so this is not necessary there.
2.1.3 The MANET IETF working group
The Internet Engineering Task Force (IETF) has set down a working group for MANET routing. This working group standardizes the IP routing protocol functionality and makes it suitable for wireless routing application for both types of topologies i.e.static and dynamic.
The basic ideas behind the designing were that:
(i) There are some unique routing interface characteristics in the wireless link interfaces and
(ii) Due to the motion or other factors, the node topologies may experience increased dynamics within a wireless routing region.
A wide diversity of protocols have been proposed, but three protocols are accepted as experimental Request for Comments (RFC)
- Ad-hoc On-Demand Distance Vector (AODV)
- Optimized Link State Routing (OLSR)
- Topology Dissemination Based on Reverse-Path Forwarding
2.2 MANET routing protocols:
As mentioned earlier, three proposed protocols have been accepted as experimental RFCs by the IETF and two of them have been presented here. Both of them are based on widely used algorithms from Internet routing. AODV uses the principals from Distance Vector routing (used in RIP) and OLSR uses principals from Link State routing (used in OSPF). The 3rd approach known as Hybrid Protocol combines the strength of both proactive and reactive schemes.
2.2.1 Reactive protocols - AODV
Reactive protocols seek to set up routes on-demand as in advance the route is not known. In the same way as mentioned above, the whole network is not known to all nodes in advance. So when a node wants to communicate with an-other node to which the route is not defined. Then the route to the destination node is established by the routing protocol. There can be a delay at the start of communication. Where the delay is not desirable one should not use the Reactive routing protocol e-g military applications etc. However, it preserves the precious node battery.
The AODV routing protocol was described in RFC 3561. The idea in AODV is like all reactive protocols, is that it transmits the topology information by node but only on-demand. When a node wants to communicate to the host and if it has no route then the route request “RREQ” will be generated by it and it will be flooded in a limited way to other nodes. It will result in an initial delay and causes the control traffic overhead to be dynamic when initiating this kind of communication. When the RREQ message reaches to the destination or to the intermediate node that have valid route entry for the destination then the route is considered found. AODV remains passive as long as a route
- Mobile Ad-hoc Working Group: Charles E. Perkins, Elizabeth M. Belding-Royer and Samir A. Das, “Ad-hoc On demand distance Vector Routing”.
exists between two endpoints but AODV will again issue a request when the route becomes invalid or lost.
There is a problem in the classical distance vector algorithm that is “counting to infinity” by using sequence numbers for all the routes, AODV avoids that. In the counting to infinity problem the nodes are updated by each other in a loop. Consider nodes N1, N2, N3 and N4 making up a MANET N1 is not updated on the fact that its route to N4 via N3 is broken. This means that N1 has a registered route, with a metric
of N2, to N4. N3 has registered that the link to N4 is down, so once node N2 is updated on the link breakage between N3 and N4, it will calculate the shortest path to N4 to be via N1 using a metric of 3. N3 receives information that N2 can reach N4 in 3 hops and updates its metric to 4 hops. N1 then registers an update in hop-count for its route to N4 via N3 and updates the metric to 5. So in this way they continue to increment the metric in a loop. This is the way that is avoided in AODV, for the example described, is by N2 noticing that N1's route to N4 is old based on a sequence number. N2 will then discard the route and N3 will be the node with the most recent routing information by which N2 will update its routing table.
27. Mobile Ad-hoc Working Group: Charles E. Perkins, Elizabeth M. Belding-Royer and Samir A. Das, “Ad-hoc On demand distance Vector Routing”.
AODV defines three types of control messages for route maintenance:
RREQ - Node transmits the route request message for requiring a route to node.
For flooding these messages AODV uses an expanding ring technique. For how many hops this message should be forwarded every RREQ carries a time to live (TTL) value that. For the first transmission this value is set to a predefined value and for the retransmission the value is increased. Retransmissions take place if there are no replies received. Data packets that are that are not transmitted yet and waiting for there transmission (i.e. the packets that initiated the RREQ) should be transmitted by a FIFO principal when a route is set.
RREP - If the node that is receiving, is either the node using the requested address or it has a valid route to the requested address a route reply message is unicasted back to the originator of a RREQ. One can unicast the message back because every route forwarding a RREQ caches a route back to the originator.
RERR - In active routes, nodes monitor the link status of next hops. The RERR message notifies all the other nodes of the loss of the link when a link breakage in an active route is detected. Each node keeps a “precursor list”, which contains the IP address for each its neighbors that are likely to use it as a next hop towards each destination in order to enable this reporting mechanism.
Figure 2-3, illustrates an AODV route lookup session. Node A wants to communicate with node J and from A to there is no route so then A broadcasts the RREQ which will be flooded in the whole network to all the nodes then this request will be forwarded from H to J, where J will generate RREP. Then by using the cached entries in H,G and D this RREP will be unicasted to A.
2.2.2 Proactive protocols - OLSR
In the proactive routing approach used in MANET maintains a constantly update topology understanding (routes calculated in advance and constantly updated).
In theory it is necessary that the whole network must be known to all of the nodes. So the constant overhead of routing traffic occurs, but there will be no initial delay in communication. Where latency delay is not desirable one should use proactive protocols because they are suitable for that kind of situations.
The (OLSR) was described in RFC3626. It is a protocol that uses the link-state scheme in an optimized manner tp circulate the topology information and it is also a table-driven pro-active protocol. Link-state information is flooded throughout the network, in a classic link-state algorithm. OLSR is also a Table-Driven Protocol. The message flooding in OLSR is optimized to preserve bandwidth because the protocol runs in wireless multi-hop scenarios. Multi Point Relaying is the technique on which the optimization is based on a technique.
As I mentioned above that the OLSR is the table-driven protocol. So, it maintains and update the information in a variety of tables.
The data on these tables is based on received control traffic, and control traffic is generated based on information retrieved from these tables. The calculation of the routes is also driven by the tables.
OLSR defines three types of control messages these are further explained in section 3.2:
I. HELLO - These are the messages that are transmitted to all the neighbors.
II. TC - These are the link state signaling which is done by OLSR. By using MPRs TC messaging is optimized in many ways.
III. MID - Nodes transmit these messages running on more than one interface. All the IP addresses are listed by these messages that are used by the node.
IV. HNA- are the messages that have function to connect a non-OLSR network to a OLSR network.
11.Giuseppe De Marco, Makoto Ikeda, Tao Yang and Leonard Barolli , “Experimental Performance Evaluation of a Pro-Active Ad-hoc Routing Protocol in Out- and Indoor Scenarios”.
- C perkins, E belding Royer, S Das.
OLSR - CORE FUNCTIONALITY
The Optimized Link State Routing Protocol is the proactive and table driven protocol & it uses a technique to reduce message flooding which is known as Multipoint Relaying. The protocol has been described in RFC 3626.
In this chapter I have discussed the functionalities of OLSR. The main function of OLSR is that it enables routing in MANET. There are some extra functions as well which can be applied when certain problems arise. e.g. when a node of MANET has a need to connect to the node of any other routing domain.
OLSR is a route maintaining protocol which never routes traffic rather it maintains the routing table which is used for package routing.
3.1 Node addressing:
Optimized Linked State Routing Protocol uses an IP address. The OLSR is made to operate on all the systems with the help of multiple communication interfaces. All the systems/nodes have their own IP addresses.
26. Hipercom Project: T. Clause and, P.Jacquet.”Optimized Link State Routing Protocol (OLSR)
Transport Protocol is used for the communication of OLSR control Messages
- Message type - As the name suggests it is the integer which identifies the message type. In OLSR we have 8 bits for message typo 0-255. but 0-127 are reserved by the OLSR and 128-255 are reserved for private.
- Vtime. 8 bits. “Indicates for how long time after reception a node MUST consider the information contained in the message as valid, unless a more recent update to the information is received. The validity time is represented by its mantissa (four highest bits of Vtime field) and by its exponent (four lowest bits of Vtime field). In other words: validity time = C*(1+a/16)* 2^b in seconds where.
a= the integer of highest four bits of Vtime.
b= the integer of lowest four bit of Vtime.
C= Scaling factor
- Message Size - The message size is of 16 bit which is the sum of the message header and the data in bytes
- Originator Address - Originator address is of 32 bits and it contains the main address of the node which generated this message.
- Time to live - It is of 8 bits, 0 to 255, it contains the maximum number of hops this message will be transmitted. The message will not be retransmitted if the TTL equals to 0 or 1 and normally a will not receive the message with TTL 0.
- Hop Count - 8 bit, Hop count is the number of Hop a message has attained. The Hop count must be incremented by 1 before the message is retransmitted.
- Message sequence number - It is of 16 bits and Originator node will assign a unique identifier number when it generates a message. This number is added into the Sequence Number field of the message. The sequence number is increased by 1 for each message originating from the node.
26. Hipercom Project: T. Clause and, P.Jacquet.”Optimized Link State Routing Protocol (OLSR).
“The protocol is an optimization of the classical link state algorithm tailored to the requirements of a mobile wireless LAN. The key concept used in the protocol is that of multipoint relays (MPRs). MPRs are selected nodes which forward broadcast messages during the flooding process. This technique substantially reduces the message overhead as compared to a classical flooding mechanism, where every node retransmits each message when it receives the first copy of the message. In OLSR, link state information is generated only by nodes elected as MPRs. Thus, a second optimization is achieved by minimizing the number of control messages flooded in the network. As a third optimization, an MPR node may chose to report only links between itself and its MPR selectors. Hence, as contrary to the classic link state algorithm, partial link state information is distributed in the network. This information is then used for route calculation. OLSR provides optimal routes (in terms of number of hops). The protocol is particularly suitable for large and dense networks as the technique of MPRs works well in this context”. .
26. Hipercom Project: T. Clause and, P.Jacquet.”Optimized Link State Routing Protocol (OLSR)
In OLSR routing all the information is sent in OLSR Packet, these packets consists of no of
headers including MAC header, IP header, UDO header and OLSR header in the last these packets have main body ( the data one wants to send ).
Packet Length: Where the size of packet is 16 bits.
Packet sequence number: Sequence number is of 16 bits.
3.2 Control traffic:
All OLSR control traffic is to be transmitted over UDP on port 698. This port is
assigned to OLSR by the Internet Assigned Numbers Authority (IANA). The RFC states that this traffic is to be broadcasted when using IPv4, but no broadcast address is specified. When using IPv6 broadcast addresses does not exist, so even though it is not specified in the RFC, it is implicit understood that one must use a multicast address in this case.
Exchanging the Control messages:
Two different types of messeges are used in OLSR for the purpose of exchanging the Control messages.
These are HELLO and Topology Control (TC).
“Contains a list of neighbors from which control traffic has been heard (but with which bidirectional communication is not yet confirmed), a list of neighbors with which bidirectional communication has been established, and a list of neighbors that have been selected to act as a Multipoint Relay for the originator of the HELLO message.”
The Address of the advertised neighbor is in the field of each Neighbor Interface Address. The status of the Link Type and the Neighbor type is in the relevant Link Code field.
The communication between the two nodes is only possible when the receiving node receives the HELLO message and finds its own address in the list of addresses to those HELLO message is sent.
The Format of HELLO message is shown in figure:
TC messages of OLSR works in the same way as the LSA- Messages in OSPF works that they disperse the link state information in the whole network, In the same way the TC message is generated by an MPR. In which its MPR selectors are listed. Since the MPRs will be selected by all the nodes among their symmetric neighbors, all the nodes as well as the link nodes and their MPRs will be diffused throughout the net and TC messages are periodically diffused. For the purpose of allowing the recipients to find out which of two TCs from the same node is the most recent the sequence number is included in each TC message.
In OLSR packets are flooded to circulate topology information throughout the network. All nodes retransmit received packets in the flooding, in its simplest form. In order to avoid the loops, a sequence number is normally carried in those packets. The receiving node then registers the sequence number to make sure that a packet is only retransmitted
once. The packet will not be retransmitted, if a node receives a packet that have the sequence number lower or equal to the last registered retransmitted packet from the sender.
Other methods are added on the wired network such as there will be no retransmission on the interface on which the packet is already arrived whereas
on the wire less multi hop network, node must have to retransmit packet on the interface on which it has arrived since this is the very nature of wireless multi-hop networks. .
This whole process again causes each re-transmitter to receive a duplicate packet from every symmetric neighbor which again transmits that packet.
3.4.1 Multipoint relaying
The concept of multipoint relaying (MPR) is to reduce the number of duplicate retransmissions while forwarding a broadcast packet. MPR limitizes set of nodes retransmitting a packet from all nodes to a subset of all nodes. Size of the subset is depending upon the topology of the network.
Restriction of retransmission of a packet is gained by making neighbors to act as Multipoint relays (MPRs). Set of MPRs is calculated by every node itself so that all Two Hop neighbors are reached through one MPR. This means that for every node n in the network that can be reached from the local node by at minimum two symmetric hops, there must exist a MPR m so that n has a symmetric link to m and m is a symmetric neighbor of the local node. the black node will be selected by Node as MPRs. All the nodes will be reached through MPR in that way. The retransmission of the traffic from node “a” will not be done by the node “b” that is to be flooded.
OLSR routing protocol allows nodes to announce willingness to act as MPRs for neighbors. There are 8 levels of willingness the lowest one is WILL_NEVER (0) which means that this node will never be chosen as a MPR, and the highest one is WILL_ALWAYS (7), which means that this node will always be chosen as a MPR. Through Hello message the willingness is spread and when calculating the MPRs this information must be considered.
3.5 Neighbor discovery:
OLSR requires a system which can detect neighbors and the communication lines to them. On a regular interval, HELLO messages illustrates a simplified form of neighbor discovery using HELLO messages.
First, an empty HELLO message is sent by A and that message is been received by B, hence registering A as an asymmetric neighbor; because in the HELLO message, B is unable to locate its own address. Now B sends a HELLO message in order to declare A as an asymmetric neighbor. As soon as A receives this message from B, it will find its own address and in this way B is set to be a symmetric neighbor. At the end, when B receives HELLO message from A, where A has already included B in that message, B will register A as a symmetric neighbor.
3.7 Routing Table Calculation :
The routing Table has the information of the number of hops to destination, local interface address, the destination address and the next address. The next address means that the next hop host. The information is provided from the HELLO Messages and from the TC Messages. The routing table will be again calculated if any changes occurs in these sets. As the OLSR is the proactive protocol so the routes for all the host in the network, ‘those who are available' must be in the Routing table and the broken link or the partially known link's information is not stored in the routing table.
The reasons because of which the routing is changed are mentioned below.
- Topological link is Appeared or lost
- The 2-hop neighbor is created or removed
- The neighbor link is appeared or disappeared
- Multiple interface association information changes.
With the aim of evaluating the cost-benefit of OLSR Protocol, simulation work was done using the NS-2 network simulator along with the OLSR implementation provided by the Hipercom project, which is called OOLSR. The only modifications made to the all-in-one (NS-2 ver. 2.27 plus OOLSR ver. 0.99.15) source code available for download were: adding packet delay measurement and, a few data outputs to generate the required data files for analysis, therefore, experimentation can be easily repeated. The simulation work was performed following the next steps. A rigorous analysis of Per Packet Delay was performed. Each experimental stage is described in the following sections.
4.1 Scenario without Data Traffic:
As a first stage, simulation was performed over static networks without sending data traffic between nodes. The objective of this stage was to achieve basic understanding on the impact of the proposed strategies. Graphical and numerical analysis was performed.
The metrics that were utilized to measure the performance of the protocol are as follow:
i. TC messages: This metric counts the number of generated TC messages only, it does not count the retransmissions.
ii. TC messages overhead: This metric counts the total amount of bytes composing all the generated TC messages.
iii. Percentage of known links: This metric counts the percentage of known links by each node, over the total amount of existing links. It is averaged over all the nodes in the network.
iv. Percentage of MPRs: This metric counts the number of nodes in the network that have been selected, by any other node, as an MPR.
4.2 Scenarios with Data Traffic:
In a second stage, data traffic was added to the simple scenarios. The objectives this time were to measure the data delivery rate and the impact of the data traffic over the achieved network topology knowledge
The same metrics than the ones for scenarios without data traffic were used plus the data delivery rate, which measures the rate and number of data packets that are properly received at the destination node.
4.3 Statistical Analysis:
Several metrics were applied in order to evaluate the performance of the protocol. Most of these metrics are averaged values over a set of simulation scenarios. The PPD metric is a metric that is averaged over all the packets properly delivered for each of the data streams and for all the mobile scenarios. Therefore, there is an averaged value for each combination of:
a. Data traffic rate
b. MPR Coverage parameter
c. TC Redundancy parameter
4.4 Experimental Results:
Simulation work was performed as described in the previous sections. In this section the corresponding results are shown.
4.4.1 Scenarios without Data Traffic
The initial simulation work which was performed over static scenarios wanted to achieve some basic understanding about protocol's performance and to get some insights on the effects of each proposed strategy to increase the topology knowledge.
Percentage of nodes selected as MPRs for different values of MPRs and TC
4.4.2 Static Scenarios with Data Traffic
In the previous section, no data traffic was sent and all the scenarios were static, therefore, it is possible to assume that at some point in time the network reaches an stability state where the topology does not change, the nodes that were chosen as MPRs do not change their status and, for the same reason, the topology knowledge does not change either. Therefore, if that is true, what has to be examined is what the impact of data traffic. With that aim one single scenario was chosen and all the different strategies and traffic rates were applied to it while keeping track second by second of the Topology Knowledge and the percentage of nodes chosen as MPRs.
The topology knowledge drop is at second 35 which means that the last set of broadcasted TC messages properly received was at second number 20, right before the data sources started sending traffic. The last because the protocol configuration says that TC message information has to be kept as valid for up to TOP_HOLD_TIME=15 seconds if no more information is received. Therefore, the lost of TC messages due to high traffic load is reflected with some delay as a decrease on the topology knowledge.
Once that the traffic load decreases the topology knowledge increases again. On the other hand, the traffic load also originates loses in terms of Hello messages, these loses are reflected as an increase on the number of MPRs
Finally, the last metric that tells about protocol performance is the data delivery rate. In this table we can clearly observe that the data delivery rate decreases with the traffic load going from 98% to 25% approx. Also the largest difference between every strategy combination, under the same traffic load, is not larger than 4%, which means that the MPR-
strategies do not have a strong impact on data delivery rates. However, we can observe that by increasing the MPR parameter from
MPR=1 to MPR=3, the data delivery rate tends to decrease, this may be due to the increased communication overhead produced by the increased number of nodes chosen as MPRs, which advertise topology information.
TRUST MODEL FOR OLSR
In chapter 4 some of the issues of OLSR have been discussed, for which a reliability model has been presented. Certain issues like precious node battery, dynamic topology, message flooding and computational overhead etc are addressed. Although it will not address all the issues encountered in OLSR routing, but of course it will help in overcoming some of the issues. Our trust model is not only applicable to OLSR Protocol but also can be extended to other routing protocols.
5.1 Aspects of Trust:
Trust is a common phenomenon. We as humans would not even be able to face the complexities of the world without resorting to trust, because it is with trust that we are able to reason sensibly about the possibilities of everyday life.
For example, we leave the house every morning trusting that we will be able to return, and will not end up in hospital because of some accident that we trust will not happen.
Trusting behavior occur when an individual perceives an ambiguous path, the result of which could be good or bad, and the occurrence of the good or bad result is contingent on the actions of another person; finally, the bad result is more harming than the good result is beneficial. If the individual chooses to go down that path, he can be said to have made a trusting choice, if not, he is distrustful.
- Trust implies some degree of uncertainty as to outcome.
- Trust implies hopefulness or optimism as to outcome.
Trust is thus strongly linked to confidence in some thing, be it the person to be trusted, the environment, or whatever it is that the desirable outcome is contingent upon. The concept of trust is choosing to put ourselves in another's hands, in that the behavior of the other determines what we get out of a situation.
In societies, trust is a fact of everyday life. Societies would no more exist without trust.
We have got so many examples to show that trust plays a vital role in societies. That we get up at all in the morning is a sign of the trust we have in society and our environment.
5.2 The Proposed Trust Model:
Our trust model is an adaptation of the trust model by Marsh (1994). It is configured for use in pure ad hoc networks. Marsh's model computes situational trust in agents based upon the general trust in the trustier and in the importance and utility of the situation in which an agent finds it-self.
General trust is the trust that one puts upon another based upon the previous experiences in different situations. Utility is considered similar to knowledge so that an agent can weigh up the costs and benefits that a particular situation holds. Importance caters for the significance of a particular situation to the thruster based upon time.
We merge the utility and importance of a situation into a single variable called weight, which is variable and increases or decreases with time. In our model we make use of trust agents that we suppose to reside on all network nodes.
Each agent operates independently and maintains its individual trust statistics. The duty of the agent is to gather data from all previous events in all states, filters it, assigns weights to each event and computes different trust levels based upon them.
Each node basically performs the following three functions:
- Trust Derivation
- Trust Quantification
- Trust Computation
5.2.1 Trust Derivation
We compute the trust in our model based upon the information that one node can gather about the other nodes. Node gathers information about other nodes in the network in passive mode i.e. without requiring any special interrogation packets. Vital information regarding other nodes can be gathered by analyzing the received, forwarded and overheard packets. In passive mode, the possible events that can be recorded are:
i. Data packets forwarded
ii. Control packets forwarded
iii. Data packets received
iv. Control packets received
v. Data packets precision
vi. Control Packets precision
The information from these events is classified into one or more trust categories. Trust categories signify the specific aspect of trust that is relevant to a particular application. For example, we might trust a particular node for the category “data forwarding” but not for the category of “Accurate Data Reception”.
5.2.2 Trust Quantification
Secure routing protocols represent trust levels by either the presence of security or its absence. We don't have others options regarding trust in routing. Trust in ad-hoc networks is always in a fluid state and is continuously changing due to the mobility of the nodes. As the period of interaction with any node may be brief, it is imperative that the trust be represented as a continual range to differentiate between nodes with comparable trust levels. The better idea would have to represent trust from -1 to +1 signifying a continuous range from complete distrust to complete trust. So the trust value would have to be stored in a floating point variable. But as we know that in ad hoc networks battery life (energy) is very precious. We can't use much of floating point variables because floating point calculation is a processing overhead: which is undesirable. So instead we use an integer value to store our results and do integer calculations.
5.2.3 Trust Computation
Trust computation involves an assignment of weights (utility/importance factor) to the events that were monitored and quantified. The assignment is totally dependent on the type of application demanding the trust level and varies with state and time. All nodes dynamically assign these weights based upon their own criteria and circumstances. For example for a particular node at a certain time control packets may be more important than data packets. So control packets with be assigned more weight than data packets. These weights have a discrete range from 1 to +10 representing the significance of a particular event from unimportant to most important. The trust values for all the events from a node can then be combined using individual weights to determine the aggregate trust level for another node. We denote this trust by T, and is given by the following equation:
T = [ Wx(i) x Tx(i) ]
Where Wi is the weight of the ith trust categoryand
Ti is the situational trustin the ith trust category.
5.3 Extension to OLSR:
In previous section our trust model is presented. This is a general model which can be extended to any protocol. But in our work we apply it to OLSR protocol.
5.3.1 OLSR Protocol
The Optimized link state routing Protocol (OLSR) protocol is a pro-active routing protocol. OLSR is an extension to LSR protocol. The most interesting feature about OLSR protocol is that each node has a set of Multi Point Relays (MPRs) and can only forward all its packets through MPRs.
5.3.2 Trust Derivation
In OLSR, we use the following two features to build up trust categories for our model:
1) Forwarded Packets (Acknowledgments)
A node can get information about the successful transmission of any packet that it sent, through the following two methods:
Using Link-Layer acknowledgments the underlying MAC protocol provides feedback of the successful delivery of the transmitted data packets.
Network Layer Acknowledgements
This method permits the sender to explicitly request a network layer acknowledgement from the next hop.
All of the above methods provide information about the successful transmission of a packet.
The method acknowledgment is further classified into two categories.
- Data packets acknowledgements
- Control packets acknowledgements
2) Received Packets
The accuracy of received data and routing packets offers a measure to compute trust levels. For instance, if routing packets are received that are found to be correct and efficient, then the originator can be allotted a higher trust value along with the set of nodes provided in that packet. The above method can be further categorized into data and control packet types and allocated different trust values as shown in Table. Counters are maintained for every received packet that are incremented based
upon the accuracy or inaccuracy of the packet.
Trust Category Forwarded (Acknowledged) Packets
The trust category PA derived from the events is based upon Packets acknowledged. The events are quantized as per the following equations to provide trust levels:
Dpa = (Dps - Dpf)
Cpa = (Cps - Cpa)
These trust levels are than assigned weights. Weights can be assigned be either assigned in a static or dynamic manner depending on their utility and importance. The situational trust T(PA) in node n for trust category PA is computed using the following equation:
T(PA)= (W(Rd) x Dpa) + (W(Rc) x Cpa)
Where W is the weight assigned to the event
Trust Category Received Packets
We derive trust category PR derived from the events based upon the Packet Received. The events are quantized as per the following equations to provide trust levels:
Dpr = (Dps - Dpf)
Cpr = (Cps - Cpf)
Pp = (Pps - Ppf)
These trust levels are than assigned weights. Weights can be assigned be either assigned in a static or dynamic manner depending on their utility and importance. The situational trust T(PR) in a node for trust category PR is computed using the following equation:
T(PR)= (W(Rd) x Dpr)+ (W(Rc) x Cpr)+ (W(Rp) x Pp)
5.3.4 Trust Computation
The situational trust values from all trust categories both categories (PA,PR) are then combined according to assigned weights, to determine an aggregate trust level for a particular node. Aggregate Trustis represented as T and given by the following equation:
T=W(PA) x T(PA) + W(PR) x T(PP)
Where W(PA)represents the weight assigned to Forwarded or Acknowledged packets and W(PR) represents the weight assigned to Received packets.
The aggregate and situational trust values are then maintained and updated for each MPR. Each node selects most trusty MPR from a set of its MPRs that have a route to the destination node. The Receiving MPR then forwards the Packets from a set of MPRs that have a route to the destination node. The routes thus found using this method may not be safe in terms of security but they all carry along an associated level of trustworthiness with them.
CONCLUSION, DRAWBACKS AND FUTURE WORK
The amount of trust established using the proposed model is currently being investigated, but inherently the model is simple, flexible and pragmatic for use in pure ad-hoc networks. Any node can receive a lot of information about the network by placing its interface into promiscuous mode. The information the node can receive can be used to build trust levels for different modes.
This model addresses OLSR routing issues in the following way:
6.1.1 Link Breakages due to Longer Links:
Finding paths between nodes that want to communicate in wireless ad hoc networks is not trivial due to network mobility, environmental conditions and constantly changing multi-hop paths (constructed by several nodes). Even more, once that the paths have been found, they have to be also maintained. Therefore, robust and efficient ad hoc routing algorithms are required. OLSR is a routing algorithm for ad hoc wireless networks that makes use of an optimized broadcasting mechanism, based on Multipoint Relay nodes (MPRs), to reduce the network load when broadcasting control messages and to support path computation. OLSR proactively provides paths to every feasible destination making use of Minimum Hop Count (MHC) as the metric to find routing paths. However, it is not very efficient due to its lack of knowledge, such as full topology, node and link status (e.g. buffer, battery, link quality, etc.) and network load when finding routing paths. Actually, MHC paths are usually constructed by longer links (between nodes located at farther distances), which tend to provide lower throughput and frequent breakage.
In Our proposed model path selection is not based on Minimum Hop Count strategy.
In our model path selection is based on trusty nodes and trusty nodes have trusty links. So the links from source to destination have more throughputs and have less frequent breakages.
6.1.2 Link breakage due to node mobility
In OLSR there is no criterion to know about the mobility of nodes. It can select routes with nodes that are mobile most of the time, so packet losses due to frequent link breakages.
In our proposed model the trust value of a node that is mobile most of the time will be low. So this link will not be selected as MPR most of the times. Only nodes that are less mobile will have greater trust value, and data will be mostly forwarded through those nodes.
6.1.3 Selecting less reliable links
OLSR is a proactive routing protocol. It means that it is most suitable in emergency situations, where loss of data is undesirable. To construct optimal paths to each destination OLSR makes use of Minimum Hop Count (MHC) as its metric, however, MHC only cares about the existence of links but not about their quality (link throughput strongly depends on link quality), therefore, two links with completely different qualities (high and poor quality) may be evenly chosen by MHC; or even worst, a one-hop path built by one poor quality link may be chosen over a two-hops path built by two high quality links. Sometime those links which are not too reliable can be selected, which is undesirable in emergency situations.
Our proposed model address this issue in the way that route is selected based on nodes reliability not on MHC. That's why loss of data is less in our model. So OLSR with our model integration is more suitable for emergency situations.
Although this model addresses some of the OLSR issues in an efficient manner, but this model has some drawbacks which are summarized below:
6.2.1 Computational Overhead
This model requires every node to do some calculation and storage at the start of sending and reception of each and every packet, consuming precious processing unit time, which makes it unusable for nodes with slow processing power.
6.2.2 Memory Usage
Every node has to maintain three tables, which consume memory. This makes the model unusable for nodes with less memory.
6.2.3 Battery Constraint
As nodes have to do a lot of computation and memory storage, which consume precious node battery.
6.3 Future Work:
We have presented a framework for trust establishment in an ad-hoc network without the existence of a central trust authority. The proposed trust model is most suitable for such networks as it operate passively and has minimal energy and computation requirements.
Currently we are implementing this model in the Network Simulator (NS-2 1989) to develop realistic feedback on the model's scalability, cost/benefit ratio and overhead of OLSR protocol.
Currently our model addresses trust calculation for MPRs only. We plan extend this model to develop routing table of OLSR based on this model. We also plan extending our model to other ad-hoc network routing protocols like AODV and DSDV. We will also look at further issues that have not been addressed here, including trust decay over time, trust acquirement through malicious behavior, malicious colluding nodes, and a security analysis of the proposed model against attacks. We also plan to include latency values in our model to differentiate between malicious and benevolent bodes.
- Hassene Bouhouch, Sihem Guemara EL Fatmi, “QoS In Ad Hoc Networks by Integreting Activity in the OLSR”. In the second Conference on Systems and Networks Communication, IEEE (ICSNC 2007).
- Dang Nguyen and Pascale Minet, “Analysis of MPR Selection in the OLSR Protocol”. In 21st International Conference on Advanced Information Networking and Application Workshops IEEE 2007
- Leila Boukhalfa, Pascale Minet and Serge Midonnet, “QoS support in a MANET based on OLSR and CBQ”. In the proceeding of Sixth International Conference on Networking (ICN'07), 2007 IEEE.
- C. Adjih, T. Clausen, P. Jacquet, A. Laouiti, P. Minet, P. Muhlethaler, etal,.Optimized Link State Routing Protocol., IETF: The Internet Engineering Task Force, October 2003, RFC 3626
- OOLSR, Implementation of the OLSR, Optimized Link State Routing Protocol,
- Hipercom Project, http://hipercom.inria.fr/oolsr , November 2004
- Extending Network Knowledge: Making OLSR a QoS Conductive Protocol by Pedro Eduardo Villanueva-Pena, Thomas Kunz Carleton University
- January, 2006
- Secure Extension to OLSR Protocol, Andreas Hafslund, Andreas Tonnesen, Roar Vjogum Rotvik, John Andersson, Oivind Kure, OLSR interop and workshop 2004.
- Sharma H.D, Gupta Anuj, “A Survey on Mobile Ad-hoc Networks”, IETE Technical Review, ISSN 0256-4602, 2003.
- Wireless security in WiFi Networks 802.11b
- IEEE Std 802.11 [ISO/IEC DIS 8802-11] Wireless LAN Medium Access Control and Physical Layer Specifications.
- Giuseppe De Marco, Makoto Ikeda, Tao Yang and Leonard Barolli , “Experimental Performance Evaluation of a Pro-Active Ad-hoc Routing Protocol in Out- and Indoor Scenarios”. In the 21st International Conference on Advance Networking and Applications(AINA'07), 2007 IEEE.
- Probabilistic approach to trust level management in Manets
- Formalising Trust as a Computational Concept, Stephen Paul Marsh
- Department of Computing Science and Mathematics University of Stirling, 1994
- Trust path calculation for OLSR, Hassan Safdar, Nust 2004
- C perkins, E belding Royer, S Das, July 2003
- ns2 Manual, www.isi.edu/nsnam/ns/doc/index.html
- Marc Greis tutorial for Network Simulator NS
- Routing and security in Manets, Nikola Milanovice, Miroslaw Malek, Humboldr university, Anthony Davidson, New York University
- Qos issues in ad hoc wireless networks, Chakrabarti and Mishra
- Natalia Vassileva and Francisco Barcelo-Arroya, “A Survey of Routing for Energy Constrained Ad Hoc Wireless Networks”. In December 2007, pp.522-527, IEEE.
- Saad Khan, Asad Amir Pirzada, “Performance Comparison of Reactive Routing Protocols for Hybird Wirless Mesh Networks”. In the 2nd International Conference on Woreless Broadband and Ultra Wideband Communications(AusWireless 2007), IEEE
- Pore Ghee Lye and John C. McEachen, “A comparison of OLSR with Traditional Routing Protocols in Marine Wireless Ad-hoc and Sensor Networks”. In the proceedings of 40th Annual Hawaii International Conference on System Sciences(HICSS 07), 2007 IEEE.
- S. Deering and R. Hinden. RFC2460 - Internet Protocol, Version 6 (IPv6) Specification, standards track edition, December 1998.
- University of Southern California Information Sciences Institute. RFC791 - Internet Protocol, standards track edition, September 1981.
- Llorenc Cerda, Michael Voorhaen, Rafael Guimaraes, Jose-M Barcelo, Jorge Garcia and Chris Blondia, “A reservation Scheme Satisfying Bandwidth QoS Constraints for Multirate Ad-hoc”.
- Hipercom Project: T. Clause and, P.Jacquet.”Optimized Link State Routing Protocol (OLSR)”.
- Mobile Ad-hoc Working Group: Charles E. Perkins, Elizabeth M. Belding-Royer and Samir A. Das, “Ad-hoc On demand Distance Vector Routing”, 2003.
- Aleksandr Hutonen, “Comparing AODV and OLSR Routing Protocol”. In the HUT T-100.551 Seminar on Internetworking.
- Thomas Heide Clausen, Emmanuel Baccelli and Garnier, “Duplicate Address Detection in OLSR Networks”.