移动通信网络：Mobile Communication Networks

Chapter 1 Introduction引言，第一章

近十年，移动通信在全世界的各个地方开始逐渐普及，而且这些移动通信设备变得越来越精巧，电池的待机时间也变得越来越长，并且机器的机体更加的坚固，更难得的是，通信协议的算法也更强悍。现在是一个无线移动的通信时代，无线技术已经逐步普及，给移动性的设备带来方便。

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 a days, Wireless Technology has taken over the Wire Communication, thus giving the facility of mobility to the users.

The main idea of mobile ad-hoc networking is to support strong and efficient operation in mobile wireless networks, by introducing the routing functionality into mobile nodes. These kinds of networks can have dynamic, sometimes rapidly-changing, multi-hop topologies which are likely composed of relatively bandwidth constrained wireless links.

Implementation Work:
 

The work this thesis covers is the modification of the Routing Protocol that is already implemented for mobile wireless networks. The entire implementation has been rewritten as before and in some aspects added. It is now implemented to comply with the RFC describing the protocol and to be as extensible as possible.

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.

As the space is limited so the background of the technical aspects will not be included in every part of this thesis. I expect that the reader has some basic knowledge of mobile ad hoc networks, UDP/TCP IP networking and C programming.

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.
 

Chapter 2 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 communication 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 Mobile ad-hoc networks (MANET). Mobile ad-hoc networks are infrastructure less where the communication between two nodes is accomplished 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:Ad-hoc网络：
 

Centralized networks, such as GSM, cannot be used in all situations. Significant examples of such scenarios where ad hoc networks can be used include establishing survivable, efficient, dynamic communication for rescue operations, disaster relief efforts and military networks. These kinds of networks cannot rely on centralized and organized connectivity and can be considered as applications of MANETs. 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’.
 

All nodes should be able to act as routers for each other, in order to enable multi-hop communication in a distributed manner (See Figure 2.1). Nodes help each other in conveying information to and fro and thereby creating a virtual set of connections between each other. Ad hoc network can only exist and operate if its nodes demonstrate a cooperative behavior.

Routing protocol sets up and maintains the Routes. Routing protocols play a vital role in the creation and maintenance of these connections. In contrast to wired networks, each node in an ad-hoc networks acts like a router. As these routers are usually on the move, standard intra-router protocols cannot be immediately adapted to ad-hoc networks. MANET routing protocol design is a complex issue considering the possible rapidly changing topology of such networks.

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.

Many different types of routing protocols have been developed for ad hoc networks and have been classified into two categories

Reactive

Proactive

In reactive routing protocols, in order to preserve precious node battery, routes are only discovered when required, while in proactive routing protocols routes are established before usage and hence avoid the delays incurred while discovering new routes in the reactive routing protocols. Reactive protocols set up traffic routes on-demand, whilst proactive protocols attempts to dynamically maintain a full understanding of the topology.
 

2.1.1 Wireless communication无线传输

Ad-hoc networks are not restricted to any special hardware. But today such networks are most likely to consist of nodes utilizing so-called WLAN interfaces . These are wireless interfaces operating according to IEEE specifications 802.11a, 802.11b or 802.11g. Throughout this document it is assumed that an ad-hoc network consists of links made up by either WLAN or Ethernet interfaces.
 

Figure: 2-1, A traditional base station scheme compared to ad-hoc multi-hop network.
 

IEEE 802.11 does not support multi-hop communication by it self. Two modes are defined for communication using WLAN devices:

Infrastructure mode: The wireless network consists of at least one access point and a set of wireless nodes. 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传统的IP路由

Routing is the primary function of IP. IP datagram’s are processed and forwarded by routers which relay traffic through paths set up by various routing protocols. Routing in today’s fixed networks is based on network aggregation combined with best matching. To maintain the knowledge about other IP Networks and IP Hosts, routing table are used by TCP/IP Hosts. IP address and a subnet mask enables to identify the Network and routes to single hosts are rarely set up. When a packet is to be forwarded, the routing table is consulted and the packet is transmitted on the interface registered with a route containing the best match for the destination. A default route is used if no network matches are found.
 

When a network interface is configured with an IP address, a route to the network address is a member, which is mostly registered on the interface automatically. Since hosts with addresses within this network are assumed to be reachable directly from this interface, the route is not set up with a gateway. This confirms that the job of the traditional IP routing is to maintain an idea of all hosts within the same subnet being on the same link. This shows that on a single one-hop network segment all of the hosts in a subnet are available, typically via routers or switches. 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.#p#分页标题#e#
 

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 groupMANET IETF工作组

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 ie ; 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:MANET路由协议：

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无协议 - 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.

Figure: 2-2 A scenario that can lead to the “counting to infinity” problem.
 

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 as illustrated in figure 2-2. 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.

Figure: 2-3 A possible path for the route reply if A wishes to find the route to J.

2.2.2 Proactive protocols – OLSR主动式协议 - 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:

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.

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.

Chapter 3 OLSR - Core Functionality

The Optimized Link State Routing Protocol (OLSR) is developed for mobile ad hoc networks. The protocol is documented in the experimental Request For Comment (RFC) 3626. OLSR is table-driven and pro-active and utilizes an optimization called Multipoint Relaying for control traffic flooding.

RFC3626 modularizes OLSR into core functionality, which is always required for the protocol to operate, and a set of auxiliary functions. The chapter presents the main functionality of OLSR. The core functionality specifies a protocol able to provide routing in a stand-alone MANET. Each auxiliary function provides additional functionalities, which may be applicable in specific scenarios, e.g., in case a node is providing connectivity between the MANET and another routing domain. All auxiliary functions are compatible, to the extent where any auxiliary function may be implemented with the core. Furthermore, the protocol is said to allow heterogeneous nodes, i.e., nodes which implement different subsets of the auxiliary functions, to coexist in the network.#p#分页标题#e#

It is important to understand that OLSR does not route traffic. It is not in any way responsible for the actual process of routing traffic. OLSR could rather be described as a route maintenance protocol in that it is responsible for maintaining the routing table used for routing packages, but such protocols are usually referred to as routing protocols.

26. Hipercom Project: T. Clause and, P.Jacquet.”Optimized Link State Routing Protocol (OLSR).

3.1 Node addressing:

OLSR uses an IP address as the unique identifier of nodes in the network. The design of the OLSR in made to be able to operate on the nodes using multiple communication interfaces, each and every node have to choose one IP address that will be its main address.

One can use OLSR on both with IP version 4(IPv4) and version 6(IPv6). The reason why IPv6 differs from IPv4 is the size of the IP addresses that are transmitted in control messages, the address to use as destination for control traffic and the minimum size of messages.

3.2 Information repositories:

As derived from the classical link-state algorithm, OLSR maintains state by keeping a variety of databases of information. These information repositories are updated upon processing received control messages and the information stored is used when generating such messages. Here follows a brief look at the different information repositories used in core OLSR.

Multiple Interface Association Information Base

This data set contains information about nodes using more than one communication interface. All interface addresses of such nodes are stored here.

23. S. Deering and R. Hinden. RFC2460, “Internet Protocol, Version 6 (IPv6) Specification”, standards track edition, December.

University of Southern California Information Sciences Institute. RFC791,” Internet Protocol”,standards track edition, September.

Link Set

This repository is maintained to calculate the state of links to neighbors. This is the only database that operates on non-main-addresses as it works on specific interface-to-interface links.

Neighbor Set

All registered one-hop neighbors are recorded here. The data is dynamically updated based on information in the link set. Both symmetric and asymmetric neighbors are registered.

2-hop Neighbor Set

All nodes, not including the local node, that can be reached via a one-hop neighbor is registered here. Notice that the two hop neighbor set can contain nodes registered in the neighbor set as well.

MPR Set

All MPRs selected by the local node is registered in this repository. The MPR concept is explained in section 3.4.

MPR Selector Set

All neighbors that have selected this node as a MPR are recorded in this repository.

Topology Information Base

This repository contains information of all link-state information received from nodes in the OLSR routing domain.

Duplicate set
 

Most information kept in these repositories is registered with a timeout. This is a value indicating for how long the registered information is to be considered valid. This value is set according to a validity time fetched from the message from which the data was last updated. The use of such a distributed validity time allows for individual message emission intervals for all nodes in the network. All database entries are removed when no longer valid according to the registered timeout. Such entries are said to be timed out.

 

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.

 

All OLSR traffic is sent in OLSR packets. These packets consist of an OLSR packet header and a body as displayed in fig 3-1.

The fields in the OLSR packet header are given on next page.

Figure: 3-1, A generic OLSR packet

Packet Length – The length in bytes of the entire packet, including the header.

Packet Sequence Number - A sequence number incremented by one each time a new OLSR message is transmitted by this host. A separate Packet Sequence Number is maintained for each interface so that packets transmitted over an interface are sequentially enumerated. An OLSR packet body consists of one or more OLSR messages. OLSR messages use a header as shown in fig 3-1.

All OLSR messages must respect this header. The fields in the header are:

Message type - An integer identifying the type of this message. Message types of 0-127 are reserved by OLSR while the 128-255 space is considered “private” and can be used for custom extensions of the protocol.
 

Vtime - This field indicates for how long after reception a node will consider the information contained in the message as valid. The time interval is represented in a mantissa-exponent format.
 

26. Hipercom Project: T. Clause and, P.Jacquet.”Optimized Link State Routing Protocol (OLSR).

Message Size - The size of this message, including message header, counted in bytes.

Originator Address – Originator Address is the main address of the originator of this message.

Time To Live - The maximum number of hops this message can be forwarded. Using this field one can control the radius of flooding.

Hop Count - The number of times the message has been forwarded.

Message Sequence Number - A sequence number incremented by one each time a new OLSR packet is transmitted by this host.

 

The core functionality of OLSR defines three message types, which will all be described in detail later. All core functionality of OLSR is based on processing and generation of these messages. However, the OLSR protocol packet format allows for a wide variety of custom packets to be transmitted and flooded to the needs of the designer. OLSR will forward unknown packet types according to the default forwarding rule as explained later. The MPR optimization used in OLSR makes this possibility for message flooding a great asset to anyone in need of net-wide broadcasting of traffic in the ad-hoc network.

26. Hipercom Project: T. Clause and, P.Jacquet.”Optimized Link State Routing Protocol (OLSR).

Figure: 3-2a Figure: 3-2b

 

OLSR uses flooding of packets 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.

The Wireless flooding structure is shown in figures: 3-2a

 

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 scenario shown in figure 3-5, 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.

 

Relaying of messages makes flooding in MANETS possible. OLSR specifies a default forwarding algorithm that uses the MPR information to flood packets. One is however free to make ones own rules for custom forwarding of custom messages. But all messages received that carries a type not known by the local node, must be forwarded according to the default forwarding algorithm. The algorithm can be outlined as:
 #p#分页标题#e#

1. If the link on which the message arrived is not considered symmetric, the message is silently discarded. To check the link status the link set is queried.

2. If the TTL carried in the message header is 0, the message is silently discarded.

3. If this message has already been forwarded the message is discarded. To check for already forwarded messages the duplicate set is queried.

4. If the last hop sender of the message, not necessarily the originator, has chosen this node as a MPR, then the message is forwarded. If not, the message is discarded. To check this, the MPR selector set is queried.

5. If the message is to be forwarded, the TTL of the message is reduced by one and the hop-count of the message is increased by one before broadcasting the message on all interfaces.

Figure: 3-5, Node A has selected the Black node as its MPR

The fact that all received unknown message types are forwarded using this approach makes flooding of special message-types possible even if these message-types are only known to a subset of the nodes.
 

Figures 3-3 and 3-4 shows the paths information is passed when being spread, first using regular flooding, then using MPR flooding. The number of retransmissions in a MPR scenario highly depends on the network topology and the MPR calculation algorithm. Using the same topology as in fig 3-2a, a possible MPR calculation could lead to the black nodes in fig 3-2b being chosen as MPRs by the center node. As one can see, if the center node is to flood a message throughout the network, 4 retransmissions are done using MPR as opposed to 24 using traditional flooding.

 

To be able to check if a message has already been retransmitted, a cache of recently processed and forwarded messages is maintained. The data stored is the minimum needed to identify the message. This means that the actual message content is not stored, but rather just originator address, message-type and sequence number. This data is cached for a constant time of DUP_HOLD_TIME suggested to be 30 seconds in the RFC. Every received message that is processed by the local node is registered in the duplicate set. If the message is forwarded, the duplicate-entry representing this message is updated accordingly; registering on what interfaces the message has been forwarded. Based on querying the duplicate set, a node can then keep track of already processed messages and already forwarded messages on a per interface basis.

 

To avoid radio collisions due to synchronized forwarding, a jitter is introduced to the message forwarding. This is a random small time interval for which the message is to be cached in the node before forwarding it. When using forwarding-jitter, piggybacking of messages will often occur since multiple messages that are to be forwarded might arrive within the buffer period. When this happens, messages are stacked within the same OLSR packet.

3.4.3 Link set optimization链接路的优化

Due to the nature of the MPR selection, only nodes which are chosen as MPRs by one or more neighbors, needs to declare their link-state. In fact, these nodes need only declare the MPR selectors in the link state messages. When this information is flooded to all nodes in the MANET, all nodes will have enough information to calculate shortest path routes to all hosts. The default OLSR setting is that a node only floods link-state messages if it is chosen as MPR by at least one neighbor, and it only announces its MPR selectors in these messages. In a topology as illustrated in figure 3-6 only the nodes selected as MPRs (gray nodes) by one or more neighbors will transmit link-state messages. One can easily see that this information, in addition to some neighbor-sensing scheme, will be sufficient to create a full understanding of the topology.

Figure: 3-6, an OLSR Routed Network
 

3.5 Neighbor discovery:周边发现

OLSR requires a system which can detect neighbors and the communication lines to them. On a regular interval, HELLO messages are sent out. Figure 3-7, illustrates a simplified form of neighbor discovery using HELLO messages.

Figure: 3-7, A Typical Neighbor Discovery session Using Hello

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.5.1 Link sensing链接发送

To keep up-to-date information on what links exist between a node and its neighbors, the link set is maintained. In HELLO messages a node emits all information about the links to neighbors from the interface on which the HELLO is transmitted. When declaring links, the IP addresses of the actual interfaces making up the link is used. When declaring the neighbor state of neighbors not reachable on the interface on which the HELLO is transmitted, the main address of the neighbor node is used.

In a scenario like the one depicted in figure 3-8, A would send the following information in its HELLO message on interface a1:

Its current link and neighbor state for d1.

Its current link and neighbor state for c1.

Its current neighbor state for the main address of node B which is b1.

When building a HELLO to be transmitted on a2, node A will include the following information:

Its current neighbor state for d1.

Its current neighbor state for c1.

Its current link and neighbor state for b2.

Figure: 3-8, Nodes A and B runs OLSR, B uses the address of b1 as its main address node D and C uses single interface

Upon receiving a HELLO from a neighbor, a node checks to see if the HELLO message contains the IP address of the interface the message was received. The link set is then updated as follows:
 

If no link entry exists for the tuple (originating IP, IP of received interface) then such an entry is created. The originating IP is fetched from the IP header of the received packet. Whenever a link entry is created a corresponding neighbor entry is created as well if no such entry exists.

An asymmetric timer is then updated according to the validity time received. This timer decides for how long the link entry is to be considered asymmetric if the symmetric timer times out.

If the address of the receiving interface is located in the received HELLO message, the symmetric timer is updated and the status of the link is updated if necessary. The status of the neighbor entry according to this link entry is also updated if necessary.

Finally the actual holding time for this entry is set to be the maximum of the asymmetric timer and the symmetric timer.

 

Neighbor detection populates the 1-hop neighbor repository and only uses the main addresses of nodes. As seen in the previous section, the neighbor entries are closely related to the link entries. Whenever a link entry is created, the neighbor table is queried for a corresponding neighbor entry. Note that this neighbor entry must be registered on the main address of the node. If no such entry can be located, then a new neighbor entry is created. This means that while a node can have several link-entries describing different

links to the same neighbor, only one neighbor entry exists per neighbor.

The status of the neighbor entries is also updated according to changes in the link-set. A neighbor is said to be a symmetric neighbor if there exists at least one link-entry in the link set connecting a local interface to one of the neighbor’s interfaces where the symmetric timer is not timed out. When a link-entry is deleted, the corresponding neighbor entry is also removed if no other link entries exist for this neighbor.

 

The MPR flooding scheme is based on the requirement that nodes have registered what neighbors have chosen them as a MPR. Nodes mark their selected MPR neighbors in HELLO messages by setting the Neighbor Type to be MPR_NEIGH.

Upon receiving a HELLO message, a node checks the announced neighbors in the message for entries matching one of the addresses used by the local node. If an entry has a matching address and the neighbor type of that entry is set to MPR_NEIGH then an entry is updated or created in the MPR selector set using the main address of the sender of the HELLO message.

 

Link state routing protocols are based on nodes flooding the network with information about their local links. In protocols like ISIS this information is mostly links to subnets, since these protocols are highly based on aggregation of networks. OLSR uses host based flat routing, so the link state emitted describes links to neighbor nodes. This is done using Topology Control (TC) messages. The format of a TC message is shown in figure 3-9.

Figure: 3-9, the OLSR Topology Control Message Format.

TC messages are flooded using the MPR optimization. This is done on a regular interval, but TC messages are also generated immediately when changes are detected in the MPR selector set. In OLSR the flooding process itself is optimized by the usage of MPRs, but as explained in section 3.4.3, the MPR technique introduces two link-state declaration optimizations as well. One should notice that more robust routing could be achieved by announcing more than the MPR selector set.#p#分页标题#e#

The MPR functionality introduces two optimizations to TC messaging:

Size optimization

The size of TC messages is reduced due to the fact that a node may only declare its MPR selectors in TC messages. The factor of this reduction is related to how dense the network topology is. In a topology as shown in figure 3-2b the TC message size of the center node would be reduced to half the size of a “classical” TC message (not including headers). When using IPv6, a simple example like this reduces a net-wide broadcast message with 64 bytes.

Sender optimization

Nodes that have no links to declare usually do not transmit TC messages. The exception here is nodes that just lost their MPR selectors. These nodes are to generate empty TC messages for a given interval to update the nodes in the MANET.

But except from this special case, if only declaring MPR selectors in TC messages, only nodes selected as MPRs will generate TC messages. Such a reduction in actual transmitted messages greatly reduces the overall overhead of control traffic.

 

The proposed heuristic for route calculation in RFC3626 is a relatively trivial shortest-path algorithm. It can be outlined as:

1. Add all one hop neighbors registered as symmetric to the routing table with a hop-count of 1.

2. For each symmetric one-hop neighbor, add all two hop neighbors registered on that neighbor that has:

Not already been added to the routing table.

A symmetric link to the neighbor.

These entries are added with a hop-count of two and next-hop as the current neighbor.

3. Then, for every added node N in the routing table with hop-count n = 2 add all entries from the TC set where:

The originator in the TC entry = N

The destination has not already been added to the routing table

New entries are added with a hop-count of n+1 and next-hop as the next-hop registered on N’s routing entry.

4. Increase n with one and do step 3 over until there are no entries in the routing-table with hop-count = n+1 [26].

5. For all entries E in the routing table the MID set is queried for address aliases. If such aliases exist an entry is added to the routing table with hop-count set to Es hop-count, and next-hop set to Es next-hop for every alias address.
 

Summary摘要

We have seen that OLSR functionality can be divided into three main modules: Neighbor sensing, multipoint relaying and link-state flooding. We have also seen that most control traffic is generated based on the set of repositories maintained by OLSR. These data sets are also updated dynamically based on received control messages.

Figure 3-10 displays an overview of the information repositories in OLSR and their relations to message processing, message generation and route calculation. Received HELLO messages trigger updates in the link set which again triggers updates in the neighbor set, which then again triggers recalculation of the MPR set. The 2 hop neighbor set is also updated based on received HELLO messages again triggering a recalculation of the MPR set. Finally the MPR selector set is updated according to information received in HELLO messages. Received TC messages triggers updates in the topology set while the MID set is updated upon receiving MID messages. All received messages will also be registered in the duplicate set if not already registered.

When generating HELLO messages, the link set, neighbor set and MPR set is queried. When generating TC messages, the MPR selector set is queried. When forwarding control traffic, the MPR selector set and the duplicate set is used.

Finally, route calculation is based on information retrieved from the neighbor set, the 2 hop neighbor set, the TC set and the MID set.

Figure: 3-10, OLSR information repositories relation overview.

Chapter 4 OLSR Implementation

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.

 

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 simulation parameters are listed in Table 4-1.

Table 4-1: Simulation parameters for static scenarios

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 simulation parameters are listed in Table 4-2.

Table 4-2: Simulation parameters for scenarios with data traffic

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

 

Simulation work was performed as described in the previous sections. In this section the corresponding results are shown.

 

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.

Some example tables are graphs are given below which will allow us to have some insight into the network and performance of OLSR in different situations.

Table 4-3: Percentages of nodes selected as MPRs for different values of MPR and TC

Table 4-3 and its corresponding graph, Graph 4-1, show how the amount of nodes selected as MPRs increase with the MPR parameter. Also, it is possible to notice that the amount of chosen MPRs is not affected by the TC strategy.

Graph 4-1: Percentage of nodes selected as MPRs for different values of MPRs and TC

 

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.

Graph 4-2 shows how the topology knowledge dramatically decreases when data traffic is injected. 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 (Graph 4-3).

Graph 4-2: Topology knowledge for MPR1 under high traffic

Graph 4-3: Percentage of MPRs for MPR=1 and TC=2 under high traffic

Finally, the last metric that tells about protocol performance is the data delivery rate and it is shown in Graph 4-4. 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-TC strategies do not have a strong impact on data delivery rates. However, we can observe that by increasing the MPR parameter from#p#分页标题#e#

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.

Graph 4-4: Topology knowledge under different Traffic rates

Chapter 5

Trust is a social good to be protected just as much as the air we breathe or the water we drink. When it is damaged, the community as a whole suffers; and when it is destroyed, societies falter and collapse.

Bok, 1978,
 

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.

 

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.

 

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.

 

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:

Link-Layer Acknowledgements

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

The number of these acknowledgements occurring with respect to every node are maintained and tabulated as shown in Table. For every packet transmitted the appropriate counter in the table for success or failure is incremented, depending if the selected MPR node has correctly forwarded it or not.

 

5.3.3 Trust Quantification

The events recorded in the tables during the trust derivation process are quantized and assigned weights so as to compute the situational trust values for different nodes.

Trust Category Forwarded (Acknowledged) Packets

The trust category PA derived from the events recorded in Table 5-1 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:#p#分页标题#e#

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 recorded in Table 5-2 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.

Chapter 6 Conclusion, Drawbacks and Future Work
 

6.1 Conclusion结论

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:

 

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.

 

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.

 

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.

Appendix A

TCL script for OLSR in NS-2

#----------------------------------------------------------------------

# Sample file for OLSR simulation

#----------------------------------------------------------------------

#----------------------------------------------------------------------

# Initialization

#----------------------------------------------------------------------

# (possibly) Remove and create result directory

set dirName "test-unicast-result"

exec sh -c "rm -rf $dirName && mkdir $dirName"

# Default node configuration

set nodeConfig "no-log 0; log-none ; log-route 1"

# Load the OOLSR as plugin

load-plugin ./oolsr-plugin --output $dirName/ns2agent.log \

multicast route packet-drop

#----------------------------------------------------------------------

# Create a simulation, with wireless support. This is basic (see ns2 doc)

#----------------------------------------------------------------------

set ns [new Simulator]

$ns color 1 Red

set val(chan) Channel/WirelessChannel

set val(prop) Propagation/TwoRayGround

set val(netif) Phy/WirelessPhy

set val(mac) Mac/802_11

set val(ifq) Queue/DropTail/PriQueue

set val(ll) LL

set val(ant) Antenna/OmniAntenna

set val(ifqlen) 25 ;#

set val(nn) 25 ;# nb mobiles

set val(rp) PLUGINPROTOCOL

set val(x) [expr $val(nn) *100.0 + 100.0]

set val(y) 1000

set topo [new Topography]

$topo load_flatgrid $val(x) $val(y)

set god [create-god $val(nn)]

$ns use-newtrace

set tracefd [open $dirName/unicast.tr w]

$ns trace-all $tracefd

set namtrace [open $dirName/unicast.nam w]

$ns namtrace-all-wireless $namtrace $val(x) $val(y)

$ns node-config -adhocRouting $val(rp) \

-llType $val(ll) \

-macType $val(mac) \

-ifqType $val(ifq) \

-ifqLen $val(ifqlen) \

-antType $val(ant) \

-propType $val(prop) \

-phyType $val(netif) \

-channel [new $val(chan)] \

-topoInstance $topo \

-agentTrace ON \

-routerTrace ON \

-macTrace OFF \

-movementTrace OFF

#----------------------------------------------------------------------

# Create nodes with OOLSR agent

#----------------------------------------------------------------------

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

set node($i) [$ns node]

$node($i) random-motion 1

$node($i) set X_ [expr $i * 100.0]

$node($i) set Y_ [expr 500.0 + ((($i * 93) % 21) - 10 ) * 10.0]

$node($i) set Z_ 0.0

$ns initial_node_pos $node($i) 20

[$node($i) set ragent_] set-config \

"$nodeConfig ; log-file-name $dirName/oolsr-node-$i.log"

# [$node($i) set ragent_] start

# [$node($i) set ragent_] config

}

#----------------------------------------------------------------------

# Sending traffic

#----------------------------------------------------------------------

set sender [new Agent/UDP]

$ns attach-agent $node(0) $sender

set cbr [new Application/Traffic/CBR]

$cbr attach-agent $sender

set receiver [new Agent/Null]

$ns attach-agent $node([expr $val(nn)-1]) $receiver

$ns connect $sender $receiver

$ns at 0.0 "$cbr start"

#----------------------------------------------------------------------

# Finishing procedure

#----------------------------------------------------------------------

proc finishSimulation { } {

global ns node val dirName

# Log the final state of all the nodes

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

[$node($i) set ragent_] state "$dirName/oolsr-node-$i.final-state"

}

# Exit

$ns flush-trace

exec nam ./test-unicast-result/unicast.nam &

exec xgraph ./test-unicast-result/unicast.tr -geometry 800x600 &

puts "Finished simulation."

$ns halt

}

#----------------------------------------------------------------------

# Run the simulation

#----------------------------------------------------------------------

proc runSimulation {duration} {

global ns finishSimulation

for {set j 1.0} {$j < $duration} {set j [expr $j * 1.3 ]} {

$ns at $j "puts t=$j"

}

$ns at $duration "finishSimulation"

$ns run

}

runSimulation 305.0

#----------------------------------------------------------------------

Appendix B

NS Plugin

#ifndef _NS_PLUGEE_H

#define _NS_PLUGEE_H

#include <set>

#include <map>

#include <queue>

#include "config.h"

#include "classifier/classifier-port.h"

#include "agent.h"

#include "copy-protocol-plugin-api.h"

//---------------------------------------------------------------------

extern std::ostream* out;

extern bool debugPlugin;

extern std::set<std::string> debugLevel;

extern PPA_PluginApi* pluginApi;

#define D(x) do { if(debugPlugin) { x; } } while(0)

#define Dl(l,x) do { std::string _s = l; \

if(debugPlugin && debugLevel.find(_s) != debugLevel.end()) { x; } } while(0)

#define Dll(l1,l2,x) \

do { if (debugPlugin \

&& ((debugLevel.find(l1) != debugLevel.end()) \

|| (debugLevel.find(l2) != debugLevel.end()))) \

{ x; } } while(0)

#define ME (*out) << Scheduler::instance().clock() <<" [plugin] node#"

<<((unsigned int)index_)<<": "

#define ME2(x) (*out) << Scheduler::instance().clock() <<" [plugin] node#" \

<<((unsigned int)x->index_)<<": "

//---------------------------------------------------------------------

class LoadPluginCommand : public TclCommand

{

public:

LoadPluginCommand();

virtual int command(int argc, const char*const*argv);

};

//---------------------------------------------------------------------

struct s_ProtocolRoute;

class PluginAgent : public Agent

{

public:

nsaddr_t index_;

void* pluginProtocolNode;

void* configData;

int configSize;

typedef struct s_ProtocolRouteCell {

struct s_ProtocolRouteCell* next;

nsaddr_t nextHopAddress;

nsaddr_t destinationAddress;

} ProtocolRouteCell;

ProtocolRouteCell* routeList;

PluginAgent(nsaddr_t id);

virtual int command(int argc, const char*const* argv);

virtual void recv(Packet* packet, Handler* handler);

void internalSendPacket(nsaddr_t srcAddress, nsaddr_t dstAddress,

void* packetData, int packetSize);

bool configureRoute(struct s_ProtocolRoute* route, int flags);

void forward(nsaddr_t nextHopAddress, Packet* packet);

// for passing packets, back to

PortClassifier *dmux_;

virtual bool processLocalPacketExtension(Packet* packet)

{ return false; }

};

//---------------------------------------------------------------------

#define PLUGIN_PROTOCOL_PACKET_TTL (64)

#define PLUGIN_PROTOCOL_MTU (1500)

const unsigned int IP_MULTICAST = 0xE000000ul;

//---------------------------------------------------------------------

extern void initMulticastExtension(PPA_PlugeeApi& simulatorApi);

//---------------------------------------------------------------------

#endif // _NS_PLUGEE_H

Appendix C

original-protocol-plugin-api.h

//---------------------------------------------------------------------

// $Id: protocol-plugin-api.h,v 1.13 2004/10/04 15:46:39 adjih Exp $

//---------------------------------------------------------------------

#ifndef _PROTOCOL_PLUGIN_API_H

#define _PROTOCOL_PLUGIN_API_H

//---------------------------------------------------------------------

#ifdef __cplusplus

extern "C" {

#endif

//---------------------------------------------------------------------

#define PPA_VERSION_MAJOR 6

#define PPA_VERSION_MINOR 0

#define PPA_FAILURE 0

#define PPA_OK 1

//---------------------------------------------------------------------

typedef struct {

void* data;

int size;

} PPA_Packet;

typedef void* PPA_PluginNode;

typedef void* PPA_PlugeeNode;

typedef void* PPA_Address;

typedef struct s_ProtocolRoute {

PPA_Address localInterfaceAddress;

PPA_Address nextHopInterfaceAddress;

PPA_Address destinationAddress;

int distance;

} PPA_Route;

#define PPA_ADD_ROUTE 1

#define PPA_DEL_ROUTE 2

//--------------------------------------------------------------

typedef struct s_PluginProtocolApi {

PPA_PluginNode (*createNodeFunction)(PPA_PlugeeNode plugeeNode,

int nbInterface,

/* borrowed: */

PPA_Address* interfaceAddressArray,

int* interfaceMTUArray,

/* borrowed: */

void* configData, int configSize);

#if 0

void (*nodeSetConfigFunction)(PPA_PluginNode pluginNode,

char* name, char* value);

char (*nodeGetConfigFunction)(PPA_PluginNode pluginNode,

char* name);

void (*nodeSetConfigFunction)(PPA_PluginNode pluginNode,

void* data, int dataSize);

#endif

void (*nodeStartFunction)(PPA_PluginNode pluginNode);

void (*nodeReceiveFunction)(PPA_PluginNode pluginNode,

PPA_Address senderAddress,

PPA_Address receiverAddress,

PPA_Packet packet); /* owned */

/* deprecated: */

void (*nodeOutputFunction)(PPA_PluginNode pluginNode, char* fileName);

void (*nodeWriteFunction)(PPA_PluginNode pluginNode,

char** result /* owned*/);

/* the following are optional, use NULL if not defined */

/* XXX: may be changed to include IP src, IP dst, ports, ... */

void (*nodeMulticastEncapsulateFunction) (PPA_PluginNode pluginNode,

PPA_Address destinationMulticastAddress,

PPA_Packet packet /* owned*/);

void (*nodeMulticastJoinGroupFunction)(PPA_PluginNode pluginNode,

PPA_Address multicastAddress);

void (*nodeMulticastLeaveGroupFunction)(PPA_PluginNode pluginNode,

PPA_Address multicastAddress);

void (*nodeMulticastSenderJoinFunction)(PPA_PluginNode pluginNode,

PPA_Address multicastAddress);

void (*nodeMulticastSenderLeaveFunction)(PPA_PluginNode pluginNode,

PPA_Address multicastAddress);

/* optional, use NULL if not defined */

int (*pluginGetExtension) (void* data1, void* data2);#p#分页标题#e#

} PPA_PluginApi;

//---------------------------------------------------------------------

typedef void (*PPA_CallbackFunction)(void* data1, void* data2, void* data3);

typedef struct s_PlugeeApi {

int addressSize;

void (*sendPacketFunction)(PPA_PlugeeNode plugeeNode,

PPA_Address srcAddress, /* of one of iface */

PPA_Address dstAddress,

PPA_Packet packet); /* owned */

int (*configureRouteFunction)(PPA_PlugeeNode plugeeNode,

/* borrowed: */

PPA_Route* route,

int flags /* add or delete */);

void (*scheduleAtFunction)(double relativeTime,

PPA_CallbackFunction function,

void* data1, void* data2, void* data3);

void (*getBroadcastAddressFunction)(PPA_Address resultAddress);

double (*getCurrentTimeFunction)();

/* optional, use NULL if not defined */

void (*sendDecapsulatedMulticastPacketFunction)

(PPA_PlugeeNode plugeeNode,

PPA_Address originatorAddress,

PPA_Address destinationAddress,

PPA_Address receiverAddress,

PPA_Packet packet /*own*/);

/* optional, use NULL if not defined */

int (*getExtension) (void* data1, void* data2);

} PPA_PlugeeApi;

//---------------------------------------------------------------------

#define PPA_InitFunctionName "protocolPluginApiInit"

typedef int (*PPA_ProtocolPluginApiInitFunc)(int major, int minor,

PPA_PlugeeApi* plugeeApi,

PPA_PluginApi** resultPluginApi);

/---------------------------------------------------------------------

/ Optional functions, offered by static_plugee.o and dynamic_plugee.o

extern int doesRequirePlugin();

extern void loadPlugin(char* fileName,

PPA_PlugeeApi* myApi, PPA_PluginApi** pluginApi);

//---------------------------------------------------------------------

#ifdef __cplusplus

} // extern "C"

#endif

//---------------------------------------------------------------------

#endif // _PROTOCOL_PLUGIN_API_H
 

References文献参考

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 21stInternational 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 21stInternational 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

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.