International Journal of Computer Networks & Communications (IJCNC)

AIRCC PUBLISHING CORPORATION

ijcnc 08

Dynamically Adaptable Improved OLSR (DA-IOLSR) Protocol

S. Vinayagam

Assistant Professor, Department of Computer Science,

Pondicherry University Community College, Puducherry, India

ABSTRACT


Optimized Link State Routing (OLSR) protocol is a proactive type of routing protocol that uses Multipoint Relay (MPR) set as the virtual backbone structure. The existing literature has identified various issues with respect to its backbone structure and has accordingly proposed improvements. In this paper, the focus is on improving the OLSR protocol by employing a Connected Dominating Set (CDS) based virtual backbone structure that is dynamically adaptable to rapid topology changes. A new Dynamically Adaptable Improved Optimized Link State Routing (DA-IOLSR) protocol is proposed that uses the local topology information to adapt the virtual backbone to topology changes. This assumes significance especially in networks that experience very high mobility. Changes in the network topology caused by node additions, node deletions and node mobility are taken care of.  Simulations are carried out to assess the performance of DA-IOLSR protocol and OLSR protocol. Packet delivery achieved by both the protocols is examined under varying mobility by using various combinations of node speed and pause time values. It is found that DA-IOLSR protocol provides better packet delivery as compared to OLSR protocol, under varying mobility conditions.

KEYWORDS


OLSR, Ad hoc network, Topology change, Virtual Backbone, Connected Dominating Set, MPR

 1.INTRODUCTION


An ad hoc network is a computer network with wireless communication links where each node has the capacity to forward the data to other nodes. The decision for determining which nodes are to forward the data and to whom are made dynamically based on the connectivity in the concerned network [1].

In ad hoc networks, ordinary nodes have to take care of routing. These nodes, however, do not have specialized equipment or fixed position in the network. Moreover, there is limited availability of resources. The lack of pre-designated routers and non-availability of physical infrastructure makes routing in ad hoc networks challenging and sets it apart from the conventional way of routing as done in wired networks. One viable solution to the said problem is flooding of messages. But flooding of control messages in ad hoc networks causes contentions and collisions, which is known as broadcast storm problem.

To facilitate routing in ad hoc wireless networks, some sort of backbone like structure needs to be built. For this, virtual backbone has been proposed, in the literature, as the routing infrastructure of ad hoc networks. The concept of virtual backbone was first proposed in [2]. Conceptually, a virtual backbone is a set of nodes that can help with routing [3]. The task of forwarding packets is restricted to these set of nodes, which would form a routing backbone.

In a wireless network employing virtual backbone, a node in the network can either be a backbone node or a non-backbone node. Any non-backbone node has to be adjacent to at least one backbone node. In addition, the set of backbone nodes has to be connected. Then, the routing path search space for each message is reduced from the whole network to the set of backbone nodes [4]. Whenever a non-backbone node wants to communicate to a destination node, it forwards the message to a neighbour backbone node. The backbone nodes in turn send the message to the destination node.

Of the varied routing protocols, Optimized Link State Routing (OLSR) protocol, a proactive type of routing protocol, uses Multipoint Relay (MPR) set as the virtual backbone for routing. The performance of OLSR protocol is largely dependent upon the virtual backbone infrastructure and it becomes imperative that MPR be very efficient for OLSR protocol to perform well. However, existing research has identified various issues in the MPR selection scheme of OLSR protocol that needs to be addressed.

Various modifications in the MPR selection scheme of the OLSR protocol have been put forth in the literature to improve the performance of the protocol. In this direction, a new improved OLSR protocol, viz., Dynamically Adaptable Improved Optimized Link State Routing (DA-IOLSR) protocol is proposed, which employs Connected Dominating Set (CDS) based virtual backbone structure that is dynamically adaptable to rapid topology changes.

The proposed protocol ensures that the virtual backbone structure remains connected even during rapid topology changes. For this, the virtual backbone structure is maintained using the local topology information whenever node additions, node deletions or node mobility occur. Thus, the need for frequent reconstruction of the virtual backbone structure, which is time and energy intensive, is eliminated. The performance of DA-IOLSR protocol is assessed against that of the OLSR protocol using simulation. The impact of node mobility on packet delivery ratio has been assessed.

The rest of the paper is organized as follows. The OLSR protocol and connected dominating set are briefly discussed in section 2. Section 3 consolidates the related work on the MPR selection scheme of OLSR and CDS which is adaptable to topology changes. Section 4 discusses the proposed DA-IOLSR protocol. The simulation environment, performance metric and the simulation results are discussed in section 5. Section 6 concludes the paper.

2.PRELIMINARIES


 2.1. Optimized Link State Routing (OLSR) Protocol

OLSR is a proactive protocol for mobile ad hoc networks, which is described in RFC 3626 [5]. It is an optimization over the classical link state protocol and works in a completely distributed manner and independently from other protocols. In the OLSR protocol, the main concept is usage of Multipoint Relays.

 A set of nodes in the symmetric 1-hop neighbourhood is selected by each and every node, to retransmit its messages. The selected set of neighbour nodes is called as the Multipoint Relay set of the node. MPR set is chosen in such a way that it covers all the symmetric strict 2-hop nodes. OLSR uses the MPRs alone to forward control traffic. Non-MPR nodes only receive and process broadcast messages; they do not retransmit broadcast messages.

In OLSR, HELLO messages and Topology Control (TC) messages are used. Periodic exchange of HELLO messages is done for populating the local link information base and the neighbourhood information base. HELLO messages are never forwarded. Each and every MPR node broadcasts TC messages to create the topology information base. The TC messages are flooded to all the network nodes and the information transmitted via the TC messages enables the nodes to populate their routing table.

2.2. Connected Dominating Set (CDS)

One of the well-known and well researched concepts used to create virtual backbone in wireless networks is CDS. It helps to overcome the broadcast storm problem and facilitates routing [6].

Given a graph G= (V,E), a Dominating Set (DS) of G is a subset C V such that each node either belongs to C or is adjacent to at least one node in C [6]. A Connected Dominating Set of G = (V,E) is a Dominating Set of G such that the subgraph of G induced by the nodes in this set is connected. The nodes in a CDS are called the dominators. The nodes other than the dominators are called the dominatees [3]. Each dominatee is dominated by a dominator [7]. The CDS with minimum cardinality is called the Minimum Connected Dominating Set (MCDS).

In CDS based routing, the dominator nodes alone maintain the routing information. A dominatee node in order to send a message to another dominatee, will send it to its dominator. Then the search space for the route is reduced to only within the CDS. When the message reaches the destination’s dominator, the message is delivered to the destination via the said dominator [8].

The network topology keeps on changing in ad hoc networks. As the authors in [9] state, a good CDS construction protocol should maintain a CDS in order to save the network resources, rather than reconstructing the whole set from scratch every time the network topology is changed. In addition, as stated in [10], the protocol should maintain and incrementally adjust the CDS when network topology changes, because of nodes either leaving or joining the network after the construction of CDS.

3.RELATED WORK


3.1 MPR Selection Scheme Of OLSR

Prior research works have suggested various improvements in the MPR selection scheme of OLSR to enhance the performance of the protocol. Authors in [11] have modified the OLSR protocol and proposed three revised MPR selection algorithms. The authors focus on supporting quality of service (QoS) routing in OLSR protocol and provide heuristics that allow OLSR protocol to find the maximum bandwidth path. The proposed heuristics are found to increase the chance of finding a path that is optimal under a bandwidth constraint.

MPR selection based on QoS measurements has been suggested in [12]. The authors state that there is no guarantee that the OLSR protocol finds the optimal widest path and show that the algorithms proposed by them do find the optimal widest paths. For MPR selection in OLSR protocol, authors in [13] present an algorithm, viz., Necessity First Algorithm (NFA). The authors state that the greedy algorithm given in RFC 3626 has problems with MPR selection. For solving the problem, they propose NFA that decreases the number of MPRs and the number of TC packets. An energy aware MPR selection mechanism for OLSR protocol to improve its energy performance in mobile ad hoc networks is provided in [14]. Based on the willingness, a modification in the MPR selection mechanism of OLSR protocol is provided.

Authors in [15] state that the OLSR protocol reduces the maintenance cost, but its selection process does not consider QoS requirements. The authors, therefore, present schemes for selecting MPRs with high efficiency. A smaller set of MPRs that give better QoS paths between any two nodes is determined with the aim of maximizing the QoS effect for a given maintenance cost. Presence of redundant control messages in the MPR concept is shown in [16]. The authors state that the redundancy is due to the MPR selection procedure. They present a cooperative MPR selection procedure that reduces the number of TC packets.

In [17], the authors examined the density of MPRs in dense wireless multi-hop networks and presented two issues. First one is that the density of MPRs is high in dense wireless multi-hop networks. Second issue is that, in dense networks, there is redundancy in the conventional MPR selection. A non-distributed heuristic algorithm is proposed that eliminates the redundancy in terms of the total number of nodes selected as MPRs.

An energy aware mechanism for MPR selection is employed in [18] to enhance the OLSR protocol. It is found that the suggested protocol optimizes the energy consumption over the network and extends the network lifetime. Authors in [19] present an enhancement of the MPR selection algorithm in OLSR protocol based on local databases of neighbour nodes extended to three hops. The enhancement is done to reduce the number of TC packets.

Authors in [20] state that the OLSR protocol specifies an algorithm that has good local properties with respect to number of MPRs selected, but does not use available information to reduce the global number of MPR nodes. The authors provide two modifications to the MPR selection strategy that are oriented to global properties, rather than local optimality.

For efficiently selecting MPR set in terms of reducing topology control traffic of OLSR protocol, a method called shared MPR selection is put forth in [21]. Since TC messages are generated by nodes selected as MPRs by their neighbours, the proposed method shares MPRs between a node and its neighbour nodes. Authors in [22] state that node mobility and signal strength condition are not considered in OLSR for MPR selection and so, OLSR protocol cannot perform well in a highly mobile network. The authors provide a protocol that improves OLSR by considering node mobility and signal strength in the selection of MPRs.

An enhanced MPR selection algorithm of OLSR protocol to select quality MPR nodes is presented in [23]. The authors state that the original MPR selection in OLSR protocol does not select quality nodes as MPR. The authors show that the proposed metric forms a more stable MPR and that the efficiency of OLSR is improved.

3.2 CDS Adaptable To Topology Changes

Connected Dominating Set (CDS) has been widely used in the literature for forming the virtual backbone in wireless networks. This section discusses the prior research work relating to CDS that is adaptable to the network topology changes.

A two-level hierarchical routing architecture for ad hoc networks is put forth in [24]. The authors provide a structure that propagates topology changes, computes updated routes in the background and provides backup routes in case of transient failures of the primary routes. Authors in [25] have provided a distributed algorithm to calculate CDS in ad hoc wireless networks. An update/recalculation algorithm for CDS is also provided that takes care of the topology changes that happen in the ad hoc wireless networks. They provide gateway updates for three types of topology changes: mobile host switching on, mobile host switching off and mobile host movement.

A message optimal distributed approximation algorithm that constructs and maintains a MCDS is provided in [26]. The proposed algorithm is fully localized and measures to handle mobility and topology changes are provided. The authors state that their algorithm is suitable in cases where frequent and unpredictable topology changes occur. Authors in [27] provide an adaptive distributed self-stabilizing algorithm. The algorithm constructs a set of vertices, which is dynamic and covers all communication needs in the network. It changes as the network topology changes and can be used as a backbone for ad hoc mobile network.

A distributed algorithm that computes a power aware CDS is presented in [28]. Localized algorithm is employed to maintain the CDS when small topology changes due to switching on/off actions of mobile hosts occur. Two versions of timer-based energy aware CDS protocols have been proposed in [10]. The authors state that, when network topology changes, their protocol maintains and adjusts CDS accordingly. Authors in [29] provide MCDS algorithm that attempts to optimize the number of messages required for constructing and maintaining the multicast backbone. When a node joins, leaves or moves away, a local route discovery and route repair process is initiated.

A CDS based Mobility Management Algorithm (CMMA) is presented in [30]. To ensure the connectivity and efficiency of CDS, the algorithm takes care of node entering, node exiting and node movement in mobile ad hoc networks. A Multi-Initiator Connected Dominating Set (MI-CDS) protocol that constructs and maintains CDS is put forth in [31]. Because of employing a small number of initiators to construct CDS, instead of using the single initiator, the corrupted CDS due to node mobility is repaired quickly.

Authors in [32] have come out with a solution that handles topology changes in ad hoc wireless networks. A general framework of the Iterative Local Solution (ILS) for calculating CDS in ad hoc wireless networks has been put forth. A virtual backbone maintenance algorithm, viz., Recyclable CDS Algorithm (RCDSA) is proposed in [33]. There are three parts in the algorithm: initial MIS and CDS construction, handling new node addition, and handling an existing node deletion. Whenever node addition or deletion occurs, the algorithm recycles the current CDS to provide a new CDS and thus is fast and efficient.

Fast Convergence Dominator Tree Construction (FC-DTC) protocol is provided in [34]. The proposed algorithm constructs CDS quickly from an initiator together with handling node mobility. Authors in [35] have employed local repair technique based on neighbourhood information, to reconstruct the alternate backbone, when the energy of a MCDS node exhausts and causes topology change. Algorithms to maintain a constant-approximate MCDS of a geometric graph under node insertions and deletions is provided in [36]. The authors ensure that the topology change that occurs when a node is inserted or deleted, affects the solution in a small neighbourhood of that node.

A distributed single-phase algorithm that constructs CDS in a single phase and handles the dynamic network topologies is presented in [37]. The required local updates alone are carried out to maintain the CDS. Authors in [38] provide a scheme that takes care of the small topology changes that occur due to deactivation of CDS node. Neighbour information is used to handle a node’s deletion from the network. An algorithm to construct MCDS, based on the rate of change of displacement and signal strength, is proposed in [39]. An algorithm that handles link failure is also proposed. Local repair algorithm is employed to reconstruct MCDS.

Authors in [40] opine that wireless network continuously changes and hence, it is necessary to adapt the MCDS to the new network topology. The authors have studied the effect of removing a non-MCDS node on the MCDS and have proposed a localized reconfiguration algorithm that is

used to obtain the MCDS of the new network topology. The proposed algorithm uses local information for reconfiguring the backbone, concentrating on computational load and message interchange. The algorithm works in two phases, testing phase and MCDS updating phase. The testing phase is used to determine removal of a non-MCDS node and if a deletion is detected, the MCDS updating phase is used.

An energy efficient optimal CDS algorithm with activity scheduling has been proposed in [41]. The proposed algorithm consists of five phases. Phase 1 is concerned with dominator election and phase 2 takes care of obtaining the connectors. Phases 3 and 4 construct optimal CDS along with activity scheduling. Phase 5, called maintenance/repair phase, carries out the maintenance of the CDS at frequent intervals. Node mobility and residual energy are considered for maintenance of the optimal CDS. The algorithm handles four cases namely, a new node joining the network, an existing node moving away, an existing dominator moving away and an existing dominator running out of energy. The authors state that the advantage of their proposed algorithm is fast convergence and longer life.

In this paper, a Dynamically Adaptable Improved OLSR (DA-IOLSR) protocol is proposed, which uses Connected Dominating Set (CDS) based virtual backbone structure that is dynamically adaptable to rapid topology changes.

4.DYNAMICALLY ADAPTABLE IMPROVED OLSR (DA-IOLSR) PROTOCOL


Dynamic network topology is one of the inherent characteristics of ad hoc networks that requires special attention. The network topology changes due to two actions of a node: either the node withdraws from a network or it joins the network. Node withdrawal refers to the functional termination of a node in the network. This may happen when a node fails, runs out of power or exits from the network. Joining refers to the functional start of a node in the network. This may happen when a new node is added to the network or when a node recovers from a failure. The mobility of a node is treated as two separate actions of withdrawal and joining. This is under the assumption that the node stops transmitting and receiving messages when in motion [37].

The changes in the network topology may render the current virtual backbone structure obsolete. Changes thus need to be made to the virtual backbone structure for the routing protocol to work. Two main approaches to handle this are: either reconstruction of the virtual backbone from scratch or maintenance of the virtual backbone. Whenever topology changes, maintenance is preferred, as construction of virtual backbone from scratch is both time and energy intensive. Moreover nodes in an ad hoc network usually have limited resources. Hence routing protocols need to be efficient enough to adapt the virtual backbone to the network topology changes by way of maintenance of the backbone.

In this direction, a new improved OLSR protocol, viz., Dynamically Adaptable Improved OLSR (DA-IOLSR) protocol is proposed. The protocol adapts the virtual backbone, constructed using CDS, to the network topology changes and is targeted at networks which face rapid topology changes. It uses local topology information to maintain the CDS, such that the virtual backbone remains connected in the event of node additions, node deletions and node mobility. The reconstruction of the virtual backbone is done upon reception of TC messages, while the maintenance of the virtual backbone is done upon reception of HELLO messages from the neighbour nodes.

The following sections explain the message format, functioning and algorithms of DA-IOLSR protocol. The algorithms in DA-IOLSR protocol work in a distributed manner.

4.1. HELLO Message Format

The format of the HELLO message as defined in RFC 3626 [5] has been modified to suit the requirements of the DA-IOLSR protocol. The new fields that are added are Status, Weight, NodeID and DomNodeID. Status of a node is used to denote whether a node is a dominator or a dominatee. Weight of a node is a weighting function to denote the importance of the node based on its degree, which refers to the number of neighbour nodes. NodeID field denotes a unique number used for identification of the node. DomNodeID field, which stands for dominator node ID, contains the ID of the node which needs to be upgraded as a dominator. As HELLO messages are never forwarded, their Time To Live (TTL) is set to 1. This way it is ensured that the HELLO messages reach only the 1-hop neighbours of a node and are not propagated any further. The information extracted from the HELLO messages is used by the DA-IOLSR protocol for maintenance of CDS.

4.2. Functioning Of DA-IOLSR Protocol

Figure 1 depicts the overall functioning of DA-IOLSR protocol. Upon reception of TC message, reconstruction of the virtual backbone from scratch is carried out using any of the available CDS algorithms. When HELLO messages are received, local topology information available through these messages is used to make changes, if required, to the CDS to compensate for the effects of the topology changes. The maintenance is also triggered upon HELLO message timer expiry.

Figure 1.Functioning of the DA-IOLSR protocol

In DA-IOLSR protocol, decisions regarding maintenance of CDS are made based on the information available about the neighbours of the node under consideration. The local topology information that is available through the HELLO messages is used to maintain the CDS so that it remains connected upon addition, deletion and mobility of nodes. Thereby, the process of maintaining CDS is quicker and proves to be efficient in terms of network performance. The global topology information which is available upon the reception of TC messages is used to reconstruct the CDS.

In OLSR protocol, the HELLO message is transmitted every 2 seconds and the TC message is transmitted every 5 seconds. In the case of DA-IOLSR protocol, the HELLO message interval is kept the same, but the TC message interval is increased to 10 seconds to delay the reconstruction process. In the intermittent time between TC messages, maintenance of CDS is carried out to handle the effects of topology changes. Also, doing so further lowers the number of control messages. As a result of this, less TC messages are transmitted and the overall network performance improves. Algorithm 1 depicts the overall functioning of the DA-IOLSR protocol.

4.3. Maintenance Of Virtual Backbone

Three types of events induce topology change. They are node addition, node deletion and node mobility. A new node, on being added to the network, uses DA-IOLSR_NodeAdd() algorithm to determine its connectivity with the CDS. An existing node, upon reception of HELLO messages, detects the deletion of nodes, if any, in the time period between the reception of the current HELLO message and the previous HELLO message.

The node using the information available from the current HELLO message, recalculates the neighbour set and compares it with the previously calculated neighbour set. If it detects deletion of a neighbour node, algorithm DA-IOLSR_NodeDelete() is called to make necessary changes, if required, to the CDS. In the case of HELLO message timer expiry, the new neighbour set would be empty, which denotes deletion of one or more existing neighbour nodes and hence algorithm DA-IOLSR_NodeDelete() is called. Node mobility is a special case of node addition and node deletion, wherein a node gets detached from one part of the network and gets attached to another part of the network. The above process is depicted in Algorithm 2.


4.4. Node Addition

There are two cases to consider when a new node gets added to the network: either the incoming node is adjacent to a dominator node or there are no adjacent dominator nodes, i.e. all its neighbour nodes are dominatee nodes. In the former case, there will be no change to the CDS as the new node gets connected to the virtual backbone via any one of its neighbour dominator nodes. In the latter case, the new node needs to identify one of its neighbour nodes that could be requested to become dominator, so that the new node gets connected to the virtual backbone. For this, the node determines the neighbour node that has got maximum weight in terms of node degree. This is done using the information obtained from the received HELLO messages.

If there is more than one node having the same maximum weight, then the node with the lowest node ID is selected. The selected node is then requested to become a dominator in the next HELLO message that originates from the new node. The neighbour node selected by the new node, on finding its ID in the DomNodeID field of the received HELLO message, upgrades itself to become a dominator. The steps for maintaining the CDS upon node addition is given in Algorithm 3.


4.5. Node Deletion

When a node leaves the network, there are two cases: either the deleted node is a CDS node or a non-CDS node. For both the cases, if the deleted node was the only neighbour of the current node, then the current node becomes an isolated node. If the deleted node was a non-CDS node, no change is necessitated to the CDS, as the deletion of a dominatee does not affect the already constructed virtual backbone.

On the other hand, if the deleted node was a CDS node, there are various cases to be considered. It is usually the case that a dominatee node may be dominated by more than one dominator. In this context, if the current node is a dominatee node, the node proceeds to determine whether it has got any dominator neighbours or not. If it has got atleast one dominator neighbour, it is connected to the virtual backbone through that node and therefore no change in CDS is necessitated on the part of the current node. If not, the current node requests its neighbour that has got the maximum weight to become a dominator to provide connectivity.

In case of more than one node having the same maximum weight, the neighbour node with the least node ID is requested to become a dominator. This request for a node to become a dominator is transmitted via the next HELLO message that originates from the current node. If the current node is a dominator node, the node proceeds to determine whether there is a break in the virtual backbone with reference to its connectivity with the neighbour nodes. If so, the dominatee neighbour node of the current node that has got the maximum weight is requested to become a dominator. The whole process of CDS maintenance owing to node deletion is depicted in Algorithm

5.SIMULATION


This section discusses the simulation environment, the performance metric and the simulation results.

5.1 Simulation Environment

The performance of DA-IOLSR and OLSR protocols is examined using NS-3 simulator [42]. A network consisting of 50 nodes is considered, which is spread across an area of 1250m x 1250m. The mobility model that is used is random waypoint mobility model wherein the node speed is varied as 5, 10 and 15 m/s. Pause time used is 2 seconds and 5 seconds. Simulation is run for a total of 500 seconds. Multiple runs were executed to extract the average values. The simulation parameters are summarized in Table 1. The performance metrics and the simulation results are discussed in the subsequent sections.

Table 1. DA-IOLSR protocol – Simulation parameters

5.2 Performance Metric

The performance of the DA-IOLSR protocol is compared with that of the OLSR protocol. The impact of mobility on packet delivery ratio of both the protocols is assessed with various node speed and pause time combinations.

Packet Delivery Ratio (PDR) is the ratio of data packets received by the destination to those generated by the source. It is calculated by dividing the number of packets received by the destination by the number of packets sent by the source.

Packet Delivery Ratio = R / S

where, R is the total number of packets received by the destination and S is the total number of packets generated by the source. A greater value of PDR implies better performance of the routing protocol.

5.3 Simulation Results

This section discusses the results pertaining to the performance of the protocols under varying mobility. Mobility is governed by the mobility model, node speed and pause time. Here, the random waypoint mobility model is used and the impact of various node speed and pause time combinations on the packet delivery ratio of DA-IOLSR and OLSR protocols is studied. For this, the node speed is varied as 5, 10 and 15 m/s, while pause time used is 2 seconds and 5 seconds.

Figures 2 to 7 shows the Packet Delivery Ratio (PDR) achieved by DA-IOLSR and OLSR protocols for the various combinations of node speed and pause time. From the results, it is observed that, for the various combinations of node speed and pause time, DA-IOLSR protocol achieves better PDR than OLSR protocol.

Figure 2. PDR of DA-IOLSR and OLSR protocols with 5 m/s node speed and 2 seconds pause time

Figure 3. PDR of DA-IOLSR and OLSR protocols with 10 m/s node speed and 2 seconds pause time

Figure 4. PDR of DA-IOLSR and OLSR protocols with 15 m/s node speed and 2 seconds pause time

Figure 5. PDR of DA-IOLSR and OLSR protocols with 5 m/s node speed and 5 seconds pause time

Figure 6. PDR of DA-IOLSR and OLSR protocols with 10 m/s node speed and 5 seconds pause time

Figure 7. PDR of DA-IOLSR and OLSR protocols with 15 m/s node speed and 5 seconds pause time

Owing to mobility, nodes leave one part of the network and get attached to another part of the network. This causes the neighbour set of the nodes to vary frequently. These topology changes may result in breakage in the connectivity of the virtual backbone. The virtual backbone structure, in such situations, do not hold good and serve its intended purpose. Hence, it needs to be either reconstructed or updated.

In the case of OLSR protocol, TC messages are transmitted every 5 seconds. Only after the expiry of this time interval, changes in the topology get disseminated throughout the network. The virtual backbone structure is reconstructed based on the new topology that is in effect at that point of time. But, in the intermittent time of reception of subsequent TC messages, as discussed earlier, the virtual backbone structure is prone to be rendered obsolete. As a result of this, packets cannot be delivered to their intended destinations due to the lack of a connected virtual backbone structure and this negatively affects the packet delivery ratio of the network.

On the other hand, the DA-IOLSR protocol relies upon HELLO messages to learn local topology information. The HELLO messages are transmitted every 2 seconds. Any topology changes that have occurred in this time gap are learnt by each of the node in the network. This information in turn is used by each node to make essential local changes to the virtual backbone to counter the effects of the topology change.

Instead of relying upon the global topology information, which is available after 10 seconds when TC messages are received, making use of the local topology information to update the CDS proves to be beneficial in terms of the performance of the protocol. As already emphasized, nodes in an ad hoc network usually have limited resources and frequent reconstruction of the virtual backbone results in exhaustion of resources, which is usually detrimental to the longevity of the nodes and hence the network. The proposed concept of maintenance of CDS is less computation-intensive as only local topology information is processed. Moreover, this update process, being done at short time intervals, reduces the time during which the CDS might be disconnected.

The virtual backbone is thereby ensured to remain connected even in the event of rapid topology changes. As a result, DA-IOLSR protocol is able to provide better PDR for various combinations of node speed and pause time, due to its dynamic adaptability to topology changes.


Figure 8. PDR of DA-IOLSR protocol for various node speed and pause time combinations

A comparison of PDR of DA-IOLSR protocol achieved for various combinations of node speed and pause time is shown in Figure 8. From the figure, it is inferred that, as the node speed increases the PDR decreases, whereas with increase in pause time the PDR increases.

6.CONCLUSION


In this paper, DA-IOLSR protocol has been proposed as an improvement over the OLSR protocol. The proposed protocol uses CDS based virtual backbone structure that is dynamically adaptable to rapid topology changes. This assumes significance especially in networks that experience very high mobility. The DA-IOLSR protocol uses local topology information to adapt the virtual backbone to topology changes due to node additions, node deletions and node mobility. The protocols, DA-IOLSR and OLSR, have been assessed in terms of packet delivery ratio under varying mobility by using various combinations of node speed and pause time values. From the simulation results, it is observed that DA-IOLSR protocol performs better under varying mobility as compared to the OLSR protocol. As part of future work, the behaviour of the proposed protocol could be examined under other mobility models and using other performance metrics.

REFERENCES


[1]     Ramjee Prasad and Albena Mihovska, New Horizons in Mobile and Wireless Communications, Volume 4: Ad Hoc Networks and Pans, Artech House, London, 2009.

[2]     Anthony Ephremides, Jeffrey E. Wieselthier, and Dennis J. Baker, (1987) “A Design Concept for Reliable Mobile Radio Networks with Frequency Hopping Signaling”, Proceedings of the IEEE, Vol. 75, No. 1, pp. 56-73.

[3]     Donghyun Kim, Yiwei Wu, Yingshu Li, Feng Zou, and Ding-Zhu Du, (2009) “Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks”, IEEE Transactions on Parallel and Distributed Systems, Vol. 20, No. 2, pp. 147-157.

[4]     Donghyun Kim, Xiaofeng Gao, Feng Zou, and Weili Wu, “Construction of Fault-tolerant Virtual Backbones in Wireless networks”, in Handbook of Security and Networks, World Scientific, Singapore, 2011, pp. 465-486.

[5]     Thomas Heide Clausen and Philippe Jacquet, (2003) “Optimized Link State Routing Protocol (OLSR)”, Available: https://www.ietf.org/rfc/rfc3626.txt.

[6]     Yingshu Li, Yiwei Wu, Chunyu Ai, and Raheem Beyah, (2012) “On the Construction of k-connected m-dominating Sets in Wireless Networks”, Journal of Combinatorial Optimization, Vol. 23, No. 1, pp. 118-139.

[7]     Sayaka Kamei and Hirotsugu Kakugawa, (2007) “A Self-stabilizing Distributed Approximation Algorithm for the Minimum Connected Dominating Set”, IEEE International Parallel and Distributed Processing Symposium (IPDPS 2007), Rome, pp. 1-8.

[8]     Yingshu Li, Shiwei Zhu, My Thai, and Ding-Zhu Du, (2004) “Localized Construction of Connected Dominating Set in Wireless Networks”, in Proceedings of US National Science Foundation International workshop on Theoretical Aspects of Wireless Ad Hoc, Sensor and Peer-to-Peer Networks (TAWN’04), Chicago, USA.

[9]     Dong Zhou, Min-Te Sun, and Ten-Hwang Lai, (2005) “A Timer-based Protocol for Connected Dominating Set Construction in IEEE 802.11 Multihop Mobile Ad Hoc Networks”, in Proceedings of the 2005 Symposium on Applications and the Internet (SAINT’05), Trento, Italy, pp. 2-8.

[10]   Bonam Kim, Junmo Yang, Dong Zhou, and Min-Te Sun, (2005) “Energy-aware Connected Dominating Set Construction in Mobile Ad Hoc Networks”, in Proceedings of 14th International Conference on Computer Communications and Networks (ICCCN 2005), San Diego, USA, pp. 229-234.

[11]   Ying Ge, Thomas Kunz, and Louise Lamont, (2003) “Quality of Service Routing in Ad-hoc Networks using OLSR”, in Proceedings of the 36th Annual Hawaii International Conference on System Sciences (HICSS’03), Big Island, USA.

[12]   Hakim Badis, Anelise Munaretto, Khaldoun Al Agha, and Guy Pujolle, (2004) “Optimal Path Selection in a Link State QoS Routing Protocol”, IEEE 59th Vehicular Technology Conference (VTC 2004), Milan, pp. 2570-2574.

[13]   Zheng Li, Nenghai Yu, and Zili Deng, (2008) “NFA: A New Algorithm to Select MPRs in OLSR”, 4th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM ’08), Dalian, pp. 1-6.

[14]   Floriano De Rango, Marco Fotino, and Salvatore Marano, (2008) “EE-OLSR: Energy Efficient OLSR Routing Protocol for Mobile Ad-hoc Networks”, IEEE Military Communications Conference (MILCOM 2008), San Diego, pp. 1-7.

[15]   Takeaki Koga, Shigeaki Tagashira, Teruaki Kitasuka, Tsuneo Nakanishi, and Akira Fukuda, (2009) “Highly Efficient Multipoint Relay Selections in Link State QoS Routing Protocol for Multi-hop Wireless Networks”, IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks & Workshops (WoWMoM 2009), Kos, pp. 1-9.

[16]   Kenji Yamada, Tsuyoshi Itokawa, Teruaki Kitasuka, and Masayoshi Aritsugi, (2010) “Cooperative MPR Selection to Reduce Topology Control Packets in OLSR”, 2010 IEEE Region 10 Conference (TENCON 2010), Fukuoka, pp. 293-298.

[17]   Teruaki Kitasuka and Shigeaki Tagashira, (2011) “Density of Multipoint Relays in Dense Wireless Multi-hop Networks”, Second International Conference on Networking and Computing (ICNC), Osaka, pp. 134-140.

[18]   Mohamed Belkheir, Zeyad Qacem, Merahi Bouziani, and Abderrahmane Ghelamellah, (2012) “An Energy Optimization Algorithm for Mobile Ad Hoc Network”, International Journal of Soft Computing and Software Engineering (JSCSE), Vol. 2, No. 10, pp. 20-26.

[19]   Abdelali Boushaba, Adil Benabbou, Rachid Benabbou, Azeddine Zahi, and Mohammed Oumsis, (2012) “Optimization on OLSR Protocol for Reducing Topology Control Packets”, 2012 International Conference on Multimedia Computing and Systems (ICMCS), Tangier, pp. 539-544.

[20]   Leonardo Maccari and Renato Lo Cigno, (2012) “How to Reduce and Stabilize MPR Sets in OLSR Networks”, 2012 IEEE 8th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), Barcelona, pp. 373-380.

[21]   Teruaki Kitasuka and Shigeaki Tagashira, (2013) “Finding More Efficient Multipoint Relay Set to Reduce Topology Control Traffic of OLSR”, IEEE 14th International Symposium  and Workshops on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), Madrid, pp. 1 – 9.

[22]   Narangerel Dashbyamba, Celimuge Wu, Satoshi Ohzahata, and Toshihiko Kato, (2013) “An Improvement of OLSR using Fuzzy Logic based MPR Selection”, 15th Asia-Pacific Network Operations and Management Symposium (APNOMS), Hiroshima, Japan, pp. 1 – 6.

[23]   Ashish Kots and Manoj Kumar, (2014) “The Fuzzy based QMPR Selection for OLSR Routing Protocol”, Wireless Networks, Vol. 20, No. 1, pp. 1-10.

[24]   Bevan Das, Raghupathy Sivakumar, and Vaduvur Bharghavan, (1997) “Routing in Ad Hoc Networks using a Spine”, in Proceedings of the Sixth International Conference on Computer Communications and Networks, Las Vegas, pp. 34-39.

[25]   Jie Wu and Hailan Li, (2001) “A Dominating-set-based Routing Scheme in Ad Hoc Wireless Networks”, Telecommunication Systems, Vol. 18, No. 1-3, pp. 13-36.

[26]   Khaled M. Alzoubi, Peng-Jun Wan, and Ophir Frieder, (2002) “Message-optimal Connected Dominating Sets in Mobile Ad Hoc Network”, in Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc’02), EPFL Lausanne, Switzerland, pp. 157 – 164.

[27]   Zhengnan Shi and Pradip K. Srimani, (2004) “A New Adaptive Distributed Routing Protocol using d-hop Dominating Sets for Mobile Ad Hoc Networks”, in Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), Las Vegas, USA, pp. 1049-1055.

[28]   Tamaghna Acharya and Rajarshi Roy, (2005) “Distributed Algorithm for Power Aware Minimum Connected Dominating Set for Routing in Wireless Ad Hoc Network”, in Proceedings of the 2005 International Conference on Parallel Processing Workshops (ICPPW’05), pp. 387-394.

[29]   M. Shukla, M. Rai, G.S. Tomar, and S. Verma, “MCDS based Multicasting in Mobile Adhoc Networks”, in Distributed Computing and Networking, Springer, Berlin Heidelberg, 2006, pp. 52-57.

[30]   Xin-yu Wang, Xiao-hu Yang, Jian-ling Sun, Wei Li, Wei Shi, and Shan-ping Li, (2008) “An Effective Connected Dominating Set based Mobility Management Algorithm in MANETs”, Journal of Zhejiang University Science A, Vol. 9, No. 10, pp. 1318-1325.

[31]   Kazuya Sakai, Fangyang Shen, Kyoung Min Kim, Min-Te Sun, and Hiromi Okada, (2008) “Multi-initiator Connected Dominating Set Construction for Mobile Ad Hoc Networks”, IEEE International Conference on Communications (ICC 2008), Beijing, pp. 2431-2436.

[32]   Jie Wu, Fei Dai, and Shuhui Yang, (2008) “Iterative Local Solutions for Connected Dominating Sets in Ad Hoc Wireless Networks”, IEEE Transactions On Computers, Vol. 57, No. 5, pp. 702-715.

[33]   Donghyun Kim, Xianyue Li, Feng Zou, Zhao Zhang, and Weili Wu, “Recyclable Connected Dominating Set for Large Scale Dynamic Wireless Networks”, in Wireless Algorithms, Systems, and Applications, Springer, Berlin Heidelberg, 2008, pp. 560-569.

[34]   Kazuya Sakai, Min-Te Sun, and Wei-Shinn Ku, (2009) “Fast Connected Dominating Set Construction in Mobile Ad Hoc Networks”, IEEE International Conference on Communications (ICC ’09), Dresden, pp. 1-6.

[35]   M. Rai, Shekhar Verma, G.S. Tomar, and Nittin Garg, (2009) “Local Repair for Extending Lifetime of Wireless Sensor Networks”, International Journal of Computer and Electrical Engineering, Vol. 1, No. 2, pp. 188-195.

[36]   Leonidas Guibas, Nikola Milosavljevic, and Arik Motskin, (2010) “Connected Dominating Sets on Dynamic Geometric Graphs”, 22nd Canadian Conference on Computational Geometry (CCCG 2010), Winnipeg MB, pp. 27-30.

[37]   Bolian Yin, Hongchi Shi, and Yi Shang, (2011) “An Efficient Algorithm for Constructing a Connected Dominating Set in Mobile Ad Hoc Networks”, Journal of Parallel and Distributed Computing, Vol. 71, No. 1, pp. 27-39.

[38]   K. P. Sampoornam and K. Rameshwaran, (2013) “An Efficient Data Redundancy Reduction Technique with Conjugative Sleep Scheduling for Sensed Data Aggregators in Sensor Networks”, WSEAS Transactions on Communications, Vol. 12, No. 7, pp. 366-375.

[39]   S. Revathi and T. R. Rangaswamy, (2014) “Efficient Flooding and Local Route Repair Using Stable Connected Dominating Set for Mobile Ad Hoc Networks”, Asian Journal of Scientific Research, Vol. 7, No. 1, pp. 102-109.

[40]   Adriana Dapena, Magda Dettlaff, Magdalena Lemańska, and Maria Jose Souto-Salorio, “Influence of a Vertex Removing on the Connected Domination Number – Application to Ad-Hoc Wireless Networks”, Centrum Zastosowań Matematyki, Poland, November 2015.

[41]   Chakradhar Penumalli and Yogesh Palanichamy, (2015) “An Optimal CDS Construction Algorithm with Activity Scheduling in Ad Hoc Networks”, The Scientific World Journal, Vol. 2015, Article ID 842346.

[42]   NS-3, Network Simulator 3, http://www.nsnam.org.

 

 

 

%d bloggers like this: