2. The Optimized Link State Routing Protocol
In this section, the functional details of OLSR vital to its implementation are discussed. This provides a background for discussing the enhancements to OLSR in the next section. OLSR is link state algorithm adapted to the requirements of a wireless LAN. The salient features of the protocol include the concept of Multipoint Relays. Hosts in the topology select amongst their neighbors, MPRs, which forward broadcast packets during the flooding process. The concept of MPRs significantly reduces the packet overhead as compared to flooding mechanism in link state routing whereby every node floods the packet when it receives its first copy. In addition, only the topology information vis-ŕ-vis the MPRs is dispensed through the network. Hence, only a small subset of links to neighbor nodes is made known in the topology. This information is then used by OLSR protocol for route calculation. As of a result, routes contain only MPRs as intermediate nodes between a source destination pair. OLSR evaluates optimal routes in terms of number of hops.
Each node broadcasts HELLO messages, with information about its neighbors and the corresponding link states. Link status can be symmetric, heard (asymmetric), or MPR. A symmetric”link is one that has been verified to be bi-directional. Heard link signifies that this node is hearing from the relevant neighbor but its not confirmed that this neighbor is also hearing from the node. The status “MPR” indicates that a node is selected by the sender as an MPR. MPR status implies that the link is symmetric too. The hello messages are broadcast to all one-hop neighbors, but are not relayed to further nodes.
The neighbor table comprises of entries with information pertaining to neighbor address (N_addr), neighbor status (N_status), the list of two hop neighbors to which this neighbor provides access (N_2hop_list). On receiving a HELLO message, the node updates the neighbor entry corresponding to the sender node. Consider the case when the entry already exists. If the node finds its own address among the addresses in HELLO message, it updates the status of the link to the sender node as SYM_LINK. Now, if the entry doesn't already exist, a new entry is recorded in neighbor table with N_addr set to the address of the sender node, N_status set to the value of SYM_LINK if the node finds its own address among the addresses listed in HELLO message, and to value ASYM_LINK otherwise. The N_2hop_list of the sender is also updated, on receiving the HELLO message. For each address listed in the HELLO message with link type SYM_LINK or MPR_LINK, if an entry with this address does not exist, it is added to the N_2hop_list.
Based on the information obtained from the hello message, each node constructs its MPR Selector table. In this table, the node registers the addresses of those one-hop neighbor nodes that have selected the node as a multipoint relay. Upon receiving a hello message, if a node finds its own address in the address list with a link type of MPR, it updates the entry corresponding to the sender node’s address in MPR selector table (or creates a new one if the entry does not already exist).
Each node in the network selects a set of nodes in its neighborhood that help in controlled flooding of broadcast messages. This set of nodes is called the Multipoint Relay (MPR) set of the node. The neighbors of the node N which are not in its MPR set, receive and process broadcast messages from the node, but do not retransmit them. The MPR set is selected such that it covers all the nodes that are two hops away. The neighborhood of a node N is the set of nodes that have a symmetric link to N. The smaller the multipoint relay set, more optimal the routing protocol.
Multipoint Relay Selectors of a node N are the nodes in neighborhood of N, which have selected N as an MPR. The node N obtains this information from periodic HELLO messages received from the neighbors. Routes to destinations in topology are calculated by incorporating only the MPRs as intermediate nodes. For accomplishing this, each node broadcasts its Multipoint Relay Selector Set (MPRSS). On receiving this information, each node evaluates or updates the route to each known destination.
The MPR set need not be optimal but it should be small enough for the concept of MPRs to be useful. However all two hop neighbors should be reachable through the selected MPRs. The algorithm for MPR selection, implemented in INRIA OLSR is described here. The algorithm at node x starts with an empty MPR set MPR(x). For all nodes y in neighbor set of node x, ( N(x) ), the degree, D(x,y) of one hop neighbor node y is evaluated. The degree of one hop neighbor node y is defined as the number of symmetric one hop neighbors of node y excluding the node x and all the symmetric one hop neighbors of node x. For each node in N(x), the number of nodes in two hop neighbor set of x ( N2(x) ) which are not yet covered by MPR(x) and are reachable through this one hop neighbor, are calculated. The node in N(x) which reaches the maximum number of uncovered nodes in N2(x) is chosen as MPR. In case of a tie, the node whose D(x,y) is greater, is selected as MPR. The steps described in this paragraph are repeated while there exist nodes in N2(x) that are not covered by MPR(x).
The TC message sent by a node in the network to declare its MPR selector set. The TC message contains the list of neighbors which have selected the sender node as a multipoint relay. The TC messages broadcast by the nodes help build topology information at each node, which in turn is useful for route evaluation.
Each node in the network maintains a topology table, in which it records the information about topology of the network as obtained from the TC messages. Each entry in the topology table contains information pertaining to the destination address (T_dest), address of the last hop to the destination (T_last) . Each such entry signifies that node T_dest has selected node T_last as an MPR and that node T_last has announced this information of its MPRSS through a TC message with the sequence number T_seq.
On receiving a TC message at a node, the message is dropped if there exists a topology table entry whose T_last is the originator of TC message and whose T_seq is greater than the sequence number of the received message (MSSN). Otherwise, all entries in the topology table whose T_last corresponds to the originator address of the TC message and whose T_seq is lesser in value than the MSSN in received message, are removed. Now, for each MPR selector address received in TC message, a new topology entry is recorded with T_dest as the MPR selector address, T_last as originator address of TC message and T_seq as the value of MSSN received in TC message. If however, such entry already existed, then the holding time of that entry is refreshed.
Routing table is evaluated based on the information in the neighbor table and topology table. Each route entry consists of the destination R_dest, the next node to the destination R_next and number of hops to the destination R_dist. Shortest path algorithm is employed for route evaluation. During a route evaluation instance, all the entries are initially removed. New route entries are recorded in the table starting with one-hop neighbors as destination nodes. Thereafter, the following procedure is executed starting with number of hops, h =1 and incrementing by 1 each time. For each topology entry, if its T_dest does not correspond to R_dest of any route entry in routing table and its T_last corresponds to R_dest of a route entry whose R_dist is equal to h, then a new route entry is recorded in the routing table with: R_dest set to T_dest, R_next set to R_next of the route entry whose R_dest is equal to T_last; and R_dist is set to h+1. The execution stops when no new entry is recorded in an iteration.
Having discussed the functionality and details of OLSR we shall now present the signal strength assessment based enhancements in the following section.