Cross Layer Optimization for Protocols in Mobile Adhoc Networks

Table of Contents

Certificate

Abstract

Acknowledgements

Tables of Contents

List of Tables

List of Figures

List of Abbreviations

CHAPTER 1 : Introduction
1.1 Mobile Adhoc Networks
1.2 Important Issues
1.3 MAC Protocols
1.4 Routing Protocols
1.4.1 Routing Protocol Strategies
1.4.1.1 Proactive strategy
1.4.1.2 Reactive strategy
1.4.1.3 Hybrid strategy
1.4.2 Destination Sequenced Distance Vector (DSDV) Routing
1.4.3 Adhoc On Demand Distance Vector (AODV) Routing 1.4.4 Dynamic Source Routing (DSR)
1.4.5 Temporally Ordered Routing Algorithm (TORA)
1.5 Cross Layer Design
1.6 Motivation for the Thesis
1.7 Problem Definition
1.8 Objectives
1.9 Contributions of the Thesis
1.10 Organization of the Thesis

CHAPTER 2 : Wireless MAC, Routing and Cross layer Protocols
2.1 Wireless MAC Protocols
2.1.1 IEEE 802.11b Standard
2.1.2 RTS-CTS-DATA-ACK four way handshake Protocol
2.3.3 Minimum Transmit Power Control Protocols
2.2 Quality of Service Routing
2.2.1 Quality of service in Adhoc Networks
2.2.1.1 Special Issues and Difficulties in MANETS
2.2.1.2 Hard state versus soft state resource reservation
2.2.1.3 Stateful versus Stateless approach
2.2.1.4 Hard QoS versus Soft QoS approach
2.2.2 Classification of QoS Approaches
2.2.3 QoS Models
2.2.3.1 IntServ
2.2.3.2 DiffServ
2.2.3.3 IntServ over DiffServ
2.2.3.4 FQMM
2.2.4 Related Work
2.3 Cross Layer Design
2.3.1 Layered vs Cross Layered approach
2.3.2 Motivations for cross layer design
2.3.3 Cross Layer Protocols

CHAPTER 3 : Link Availability Model
3.1 Link Prediction
3.1.1 Link Prediction Algorithm
3.2 Simulation and Results
3.2.1 Simulation Parameters
3.2.2 Performance Metrics
3.2.3 Simulation Results and Analysis
3.2.3.1 CBR Simulations
3.2.3.2 Energy Simulations
3.2.3.3 TCP Simulations
3.3 Summary and Future Work

CHAPTER 4 : Dynamic Power Control wireless adhoc MAC Protocol
4.1 Dynamic Power Control wireless adhoc MAC Protocol
4.2.1 Proposed Protocol Basics
4.2.2 Model Description
4.2.3 Proposed Protocol Description
4.2.4 Proposed Protocol Algorithm
4.2 Simulation and Results
4.2.1 Simulation Parameters
4.2.2 Performance Metrics
4.2.3 Results and Analysis
4.3 Summary and Future work

CHAPTER 5 : Cross Layer Design for Power Control and Link Availability
5.1 Cross Layer Power Control and Link Availability Prediction
5.1.1 Power Control
5.1.2 Link Availability
5.1.3 Proposed Protocol Algorithm
5.2 Simulation and Results
5.2.1 Simulation Parameters
5.2.2 Performance Metrics
5.2.3 Simulation Results and Analysis
5.3 Summary and Future Work

CHAPTER 6 : Conclusion and Future Work
6.1 Contributions
6.2 Conclusions
6.3 Future Work

Bibliography

Abstract

Advances in wireless technology and hand-held computing devices have brought revolution in the area of mobile communication. The increasing mobility of humans across the globe generated demand for infrastructure-less and quickly deployable mobile networks. Such networks are referred to as Mobile Adhoc Networks (MANET). Usually, nodes in a MANET also act as a router while being is free to roam while communicating each others. Adhoc networks are suited for use in situations where infrastructure is unavailable or to deploy one is not cost effective.

Frequent changes in network topology due to mobility and limited battery power of the mobile devices are the key challenges in the adhoc networks. The depletion of power source may cause early unavailability of nodes and thus links in the network. The mobility of nodes will also causes frequent routes breaks and adversely affects the required performance for the applications.

Availability of a route in future mainly depends on the availability of links between the nodes forming the route. Therefore, it is important to predict the future availability of a link that is currently available. We have proposed an analytical model for link prediction using Newton divided difference method. This link availability algorithm is incorporated in AODV routing algorithm (AODVLP) to evaluate the performance of AODV routing protocol using the metrics viz. delivery rate, average end-to-end delay, average RTS collisions per node and route failure. In the existing AODV protocol, packets are routed until a link in the existing path fails. This results in degradation of quality of service of network in terms of end-to-end delay and delivery ratio. In this thesis, we have modified AODV routing protocol by incorporating link prediction algorithm using proposed link prediction model. This algorithm predicts the link availability time and even before the link breaks; either it repairs the route locally or send information to the source nodes to enable them initiating a new route search well in time. This algorithm improves the quality of service of the network. Simulation results show that AODV routing algorithm with link availability model performs better than the existing AODV.

In adhoc networks, MAC protocols are responsible for the coordinated access from the active nodes. Various MAC protocols with different objectives have been proposed for adhoc networks. Maximizing the nodes’ lifetime and thus the network lifetime is a common objective of adhoc networks. Since the adhoc nodes are assumed to be dead when they are out of battery, it is imperative to optimize the battery consumption at the nodes.

Another main objective is increase the capacity of the networks. We have proposed dynamic power control wireless adhoc MAC protocol (DPCP) based on modification to RTS-CTS-DATA-ACK handshake in context to IEEE 802.11 and have shown that the proposed scheme saves energy and increases throughput as compared to IEEE 802.11b std.

Several researches have proposed cross layer interactions at various layers with different objectives. However, we have proposed a cross layer design for power control and link availability (DPCPLP) in mobile adhoc networks to address both the issues of availability of links due to mobility and of increase of the battery life of the nodes. This method uses interaction of non adjacent layers e.g. physical and network layers for prediction of links break and optimization of power at MAC layer. The received signal strength and transmit power of the packets are used as cross layer interaction parameters. The proposed method performs better than IEEE 802.11 and AODVLP in terms of increased throughput, better packet delivery ratio and decreased average communication interruption time, less routing overheads, less end-to-end delay and lower energy consumption. The performance evaluation of proposed protocols is conducted using ns-2 network simulator. All the simulation results show that the proposed protocols perform better than the other protocols.

Dedicated

To

My Maa & Papa

ACKNOWLEDGEMENTS

I owe my profound gratitude to my thesis supervisor Dr. Yatindra Nath Singh, Professor, Indian Institute of Technology, Kanpur for his valuable guidance, supervision and persistent encouragement. Due to the approach adopted by him in handling my thesis and the way he gave me freedom to think about different things, I was able to do constructive thesis. By working under him I have gained priceless knowledge as to how to go about doing an effective research.

I would also like to express my sincere thanks to Dr. Raghuraj Singh, Professor, Computer Science and Engineering Department, Harcourt Butler Technological Institute, Kanpur for his exceptional guidance, ideas and continuous support during the research work.

It is extremely hard to find words that express my gratitude to my parents, husband Sharad Kumar Yadav, IOFS and most loving sons Amod Yadav and Aryan Yadav for their invaluable help over all these years. I wish them all good luck in their bright carrier and future plans. They gave me courage and strength whenever I needed it and supported me in every possible way throughout these years.

I take this opportunity to thank all the associated faculty members and friends for the precious time they devoted for help, feedback and encouragement during the course of my research work.

Finally, I express my gratitude towards The Almighty God for showering His blessings upon me.

List of TABLES

Table 3.1 Simulation parameters for AODVLP

Table 4.1 Simulation parameters for DPCP

Table 5.1 Simulation parameters for DPCPLP

List of Figures

Figure 1.1 Hidden and exposed terminal problem

Figure 1.2 Classification of MAC Protocols

Figure 1.3 Categorization of Adhoc Routing Protocols

Figure 2.1 RTS-CTS-DATA-ACK four way handshake MAC Protocol

Figure 2.2 Classification of QoS approaches

Figure 2.3: The layered and the cross layer architecture

Figure 3.1 Local route repair

Figure 3.2 Route failures vs nodes

Figure 3.3 Packet delivery ratio vs nodes

Figure 3.4 Average RTS collisions per node vs nodes

Figure 3.5 End-to-end delay vs nodes

Figure 3.6 Route failures vs node velocity

Figure 3.7 Packet delivery ratio vs node velocity

Figure 3.8 Average RTS collisions per node vs node velocity

Figure 3.9 End-to-end delay vs node velocity

Figure 3.10 Successfully data transmission rate vs traffic generated rate

Figure 3.11 Average energy consumption (in Joules) per communication of 1 Kbyte of data vs traffic generated rate

Figure 3.12 Throughput per node vs nodes

Figure 3.13 Energy consumption per communication of 1 kilobyte data vs nodes

Figure 3.14 Packet delivery ratio vs nodes

Figure 3.15 End-to-end delay vs nodes

Figure 3.16 Packet delivery ratio vs node velocity

Figure 3.17 End-to-end delay vs node velocity

Figure 4.1 Successfully data transmitted vs traffic generated rate

Figure 4.2 Average energy consumption (in Joule) per communication of 1 kilobyte of data vs traffic generated rate

Figure 4.3 Successfully 1 kilobyte of data transmitted vs density

Figure 4.4 Average energy consumption (in Joule) per communication of 1 kilobyte of data vs density

Figure 5.1 Cross layer interactions at node

Figure 5.2 Format of Optimum Power Table

Figure 5.3 Average interruption time vs node velocity

Figure 5.4 Routing overhead vs node velocity

Figure 5.5 Average interruption time vs packet generation rate

Figure 5.6 Routing overhead vs packet generation rate

Figure 5.7 Throughput vs packet generation rate

Figure 5.8 Average energy consumption (in Joule) per communication of 1 Kbyte of data vs packet generation rate

Figure 5.9 Throughput per node vs no. of nodes

Figure 5.10 Energy consumption per communication of 1 kilobyte data vs no. of nodes

Figure 5.11 Delivery of packets vs no. of nodes

Figure 5.12 End-to-end delay vs no. of nodes

List of ABBREVIATIONS

Abbildung in dieser Leseprobe nicht enthalten

CHAPTER 1

Introduction

1.1 Mobile Adhoc Networks

Historically, Mobile Adhoc Networks (MANETs) have been primarily used in tactical network-related applications to improve battlefield communications. Early adhoc network can be traced back to DARPA Packet Radio Network Project (PRNET) in 1970s. The PRNET project used ALOHA [1] and subsequently used CSMA approaches to support the dynamic sharing of the radio resources, and featured multi-hop communication among nodes by introducing several distance vector routing protocols. In the early 1990, the U.S. Department of Defense continued to support research programs such as Global Mobile Information Systems (GLOMO) and the Near-Term Digital Radio program (NTDR).

The recent advances in miniaturization, and the proposal of open standards (Bluetooth, IEEE 802.11, RFID) for wireless communication, have greatly facilitated the deployment of adhoc networks and support for more advanced functions. This allows a node to act as a wireless terminal as well as a repeater and still be compact enough to be mobile. A self organizing adaptive collection of such devices connected with wireless links is said to be an Adhoc network. A wireless network is normally a decentralized network. The network is adhoc because each node is willing to forward data for other nodes, and so the determination of which nodes forward data is made dynamically. This is in contrast to wired networks in which routers perform the task of routing. It is also in contrast to managed (infrastructure) wireless networks, in which a special node known as an Access point manages communication among other nodes.

Since the adhoc network is a decentralized network it should detect any new nodes automatically and induct them seamlessly. Conversely, if any node moves out of the network, the remaining nodes should automatically reconfigure themselves to adjust to the new scenario. If nodes are mobile, the network is termed as a MANET (Mobile Adhoc NETwork). The Internet Engineering Task force (IETF) has setup a working group named MANET for developing standards for these networks.

Typically there are two types of architectures in adhoc networks: flat and hierarchical [2, 3]. Each node in an adhoc network is equipped with a transceiver, an antenna and a power source. The characteristics of these nodes can vary widely in terms of size, processing ability, transmission range and battery power. Some nodes can act as servers, others as clients and few others may be flexible enough to act as both depending on the situation. In certain cases, each node may need to act as router in order to convey information from one node to another [4].

The decentralized nature of the Adhoc wireless networks makes them suitable for variety of applications where the central nodes cannot be relied upon. It also improves the scalability of wireless Adhoc networks as compared to wireless managed networks. Also Adhoc networks have the ability to easily integrate with the existing infrastructure oriented network thereby increasing the scope of their applications [3, 5]. Some of the applications are given as follows:

a) When a disaster occurs, it is possible that existing communication infrastructure might fail completely and restoring communication quickly is crucial. In such situation, an adhoc wireless network featuring wideband capabilities can be used to provide crisis management services. By using a mobile adhoc network, a communication infrastructure could be setup in hours instead of weeks.
b) Wireless adhoc networks have applications in vehicular technology and are called Vehicular Adhoc Wireless networks. In these networks, vehicles communicate with each other and possibly with roadside infrastructure. A long list of applications varying from transit safety to driver assistance and internet access can be provided to users through these.
c) In battlefields, there is no possibility of having infrastructure oriented network. An adhoc network can be easily deployed in such areas and help in proper coordination amongst the soldiers.
d) Adhoc network can be used during travel for household applications, in telemedicine, for virtual navigation, etc.

1.2 Important Issues

There are several important issues in adhoc wireless networks. Most adhoc wireless network applications use industrial, scientific and Medical (ISM) band that is free from licensing formalities. Since wireless is a tightly controlled medium, it has limited channel bandwidth that is typically much less than that of wired networks. Besides, the wireless medium is inherently error prone. Even though a radio may have sufficient channel bandwidth, factors such as multiple-access, signal fading, noise and interference can cause significant throughput loss in the wireless networks. Since wireless nodes may be mobile, the network topology can change frequently without any predictable pattern. Usually the links between nodes are bi-directional, but there may be cases when differences in transmission power give rise to unidirectional links, which necessitate special treatment of the medium Access control (MAC) protocols. Adhoc network nodes must conserve energy as they mostly rely on batteries as their power source. The security issues should be considered in the overall network design, as it is relatively easy to eavesdrop on wireless transmission. Routing protocols require information about the current topology, so that a route from a source to destination may always be found, if possilble. However, the existing routing schemes, such as distance vector and link state based protocols, lead to poor route convergence and low throughput for the dynamic topologies. Therefore a new set of routing schemes such as Destination Sequenced Distance Vector (DSDV) [6], Dynamic source routing (DSR) [7], Adhoc On-Demand Distance Vector routing (AODV) [8] and Temporally Ordered Routing Algorithm (TORA) [9] have been developed.

MAC layer is also referred as a sub layer of the ‘Data Link layer”. It involves functions and procedures necessary to transfer data between two or more nodes in a network. It is the responsibility of the MAC layer to perform error detection for the anomalies occurring in the physical layer. The layer performs specific activities for framing, physical addressing, flow control and error control. It is responsible for resolving conflicts among different nodes for channel access. Since the MAC layer has a direct bearing on how reliably and efficiently data can be transmitted between two nodes along the routing path in the network, it affects the Quality of Service (QoS) in the network. The design of MAC protocol should also address issues caused by mobility of nodes and unreliable time varying channels.

1.3 MAC Protocols

The MAC protocols developed for wired networks like Carrier Sense Multiple Access and its variations such as CSMA with Collision Detection (CSMA/CD) cannot be directly used in wireless networks. In CSMA based schemes, the transmitting node first senses the medium to check whether it is idle or busy. The node defers its own transmission to prevent a collision with the existing signal, if the medium is sensed busy. Otherwise, the node begins to transmit its data while continuing to sense the medium. But in the wireless networks, the collisions occur at the receiving node. Since, signal strength in the wireless medium fades away in the proportion to the square of the distance from the transmitter, the presence of the signal at the receiver node may not be clearly detected at the other sending terminals, if they are out of range.

As shown in the figure 1.1, node B is within the range of nodes A and C, but C is not in the range of A. Let us consider the case where A is transmitting to node B. Node C, being out of A’s range, cannot detect carrier and may send data to B, thus causing a collision at B. This is referred to as the ‘hidden terminal problem’, as nodes A and C are hidden from each other [10, 11].

Let us consider another problem which we face in wireless networks. In this case, node B is transmitting to node A. Since C is within B’s range, it senses carrier and decides to defer its own transmission. However this is unnecessary because there is no way C’s transmission can cause any collision at receiver A. This is referred as the ‘exposed terminal problem’, since B being exposed to C caused the later to needlessly defer its transmission [11].

Abbildung in dieser Leseprobe nicht enthalten

Figure 1.1: Hidden and exposed terminal problem

Apart from above mentioned problems, adhoc wireless networks have another limitation of having limited energy or battery life. This problem is quite severe because once the battery of the node is exhausted; it cannot transmit as well as receive any data. It becomes dead and this affects the network connectivity since in the adhoc network when an intermediate node dies off, the whole link has to be formed again. This leads to large amount of delay thereby hampering the throughput of the whole system. Hence the power control is a very important aspect in Wireless Adhoc network.

There are various types of MAC protocols developed for wireless adhoc networks; they are classified as shown in the figure 1.2. In contention free MAC schemes (e.g. TDMA, FDMA, CDMA), certain assignments are used to avoid contentions [3]. Contention based schemes on the other hand, are aware of the risk of collisions of transmitted data. Since contention free MAC schemes are more applicable to networks with centralized control, we shall focus on contention based MAC schemes in this thesis.

Abbildung in dieser Leseprobe nicht enthalten

Figure 1.2: Classification of MAC Protocols

The contention based MAC protocols can be divided into two groups known as Random Access and Reservation/ Collision Resolution MAC protocols. In Random access based schemes, such as ALOHA, a node may access the channel as soon as it is ready. Naturally, more than one node may transmit at the same time, causing collisions. ALOHA is more suitable under low system loads with large number of potential senders and it offers relatively low throughput. A variation of ALOHA, termed ‘Slotted ALOHA’, introduces synchronized transmission time slots similar to TDMA. In this case, nodes can transmit only at the beginning of the time slot. The introduction of time slot doubles the throughput as compared to the pure ALOHA scheme, with the cost of necessary time synchronizations. The CSMA based schemes further reduce the possibility of packet collisions and improve the throughput.

In order to solve the hidden and exposed terminal problems in CSMA, researchers have come up with many protocols, which are contention based but involve some forms of dynamic reservation/ collision resolution. Some schemes use the Request to Send (RTS)/ Clear to Send (CTS) control packets to prevent collisions, e.g. Multiple Access Collision avoidance (MACA) [12], MACA for wireless LANs (MACAW) [13] and also Wi-Fi 802.11 Std.

The contention based MAC schemes can also be classified as sender initiated or receiver initiated [3], single channel or multiple channel, power aware, directional antenna based and unidirectional link based schemes. The dynamic reservation approach involves the setting up of some sort of a reservation prior to data transmission. If a node that wants to send data takes the initiative of setting up this reservation, the protocol is considered to be a sender initiated protocol. Most schemes are sender initiated. In a receiver initiated protocol, the receiving node polls the potential transmitting nodes for data. If a sending node indeed has data for some receiver, it is allowed to transmit after being polled. The MACA – By invitation (MACA-BI) [14] and Receiver Initiated Busy Tone Multiple Access (RI-BTMA) [15] are examples of such schemes. MACA-BI is efficient in terms of transmit and receive turnaround times compared to MACA.

Another classification is based on the number of channels used for data transmission. Single channel protocols set up reservation for transmissions, and subsequently transmit their data using the same channel or frequency. Many MAC schemes like those mentioned earlier (MACA, MACAW and IEEE 802.11 Std.) use single channel. Multiple channel protocols use more than one channel in order to coordinate connection sessions among the transmitter and receiver nodes. The FCC mandates that all radios using ISM band must employ either DSSS or FHSS schemes. Several MAC protocols have been developed for using multiple channels through frequency hopping techniques, e.g. Hop-reservation multiple Access (HRMA) scheme [16]. Some others use special control signal on a separate channel for protecting the actual data that is transmitted on the data channel. For e.g. DBTMA (Dual Busy Tone Multiple Access) [17] has two narrow band signaling channels and one data channel. Two narrow bands send signals to protect the RTS and the DATA packets are sent on the data channel. This scheme achieves very high throughput and has negligible collisions. But disadvantage of this scheme is its high power consumption. It consumes almost double power as compared to IEEE 802.11 Std. protocol [18-21].

As we know, Adhoc Network has a major limitation of energy resource at each node. When a node dies it cannot forward packets to other nodes thereby hampering the connectivity of the network. Hence there has been a lot of research done in developing power aware protocols for the Adhoc networks. The power aware protocols are also divided depending upon which parameter the protocol is using to minimize the energy consumption e.g. optimizing the transmission power level. Such types of protocols which alter the transmission power level are known as Transmission Power Control Power Aware protocols. In the section given as follows, we explain all the transmission power control protocols with their advantages and disadvantages.

In the OPCM Optimistic Power Control MAC Protocol for Mobile Adhoc Networks [22], different power control mechanisms are used in the transmission and retransmission stages. The power level of the data packet is adjusted every time the DATA packet is retransmitted. In this protocol, the RTS and CTS packets are transmitted at maximum power level and the DATA and the ACK packets are sent at minimum required power level (or the desired power). This desired power level varies from minimum power level required to the maximum power level at which a node can transmit a packet. But this protocol has some disadvantages. In this MAC protocol the ACK packet is not completely protected by the RTS packet. The RTS is transmitted at maximum power levels and because the nodes reset the NAV which was initialized due to reception of RTS when they don’t receive start of the DATA packet within a predefined time interval, the collision of ACK packets may happen. Hence the throughput of OPCM is less than that of the IEEE 802.11 Std. Since OPCM protocol transmits RTS and CTS packet at maximum power level hence the throughput of the system doesn’t increase as it is not making use of spatial reusability.

Another Wireless power aware MAC protocol is Power Control Medium Access Control (PCMAC) which tries to solve one of the disadvantages of OPCM MAC protocol. In this scheme [23], the RTS and CTS packets are sent with using the maximum power, whereas the DATA and ACK packets are sent with just the minimum power required for communication between the sender and receiver. They use closed loop power control in which the CTS and the DATA contain the feedback which tells the other node at what minimum power to transmit the packet in such a way that this node receives the packet. The source node periodically transmits the DATA packet at the maximum power level, for just enough time so that the nodes in the carrier sensing range, such as A may sense it. The scheme achieves considerable improvement in power consumption but since the error floor reserved with the use of RTS and CTS is same as that of the IEEE 802.11 Std, the throughput doesn’t improve. Due to periodic transmission of DATA packets at maximum power, the throughput doesn’t degrade. But the complexity of the transceiver device increases due to fast and periodic change of transmission power thereby increasing the cost. This protocol achieves higher throughput than the OPCM protocol.

In Minimum Power control in Adhoc Networks [24, 25], the transmission power is dynamically changed in such a way that it is the minimum required for a packet to reach the intended receiver. These protocols also use RTS, CTS, and DATA for communication but all the packets are sent at minimum power. There are two MAC protocols based on the mentioned principle. The Minimum Power Control achieves considerable amount of power saving as well as improvement in throughput as compared to IEEE 802.11 standard.

1.4 Routing Protocols

Due to the dynamic nature of MANETs, designing communications and networking protocols for these networks is a challenging process. One of the most important aspects of the communication process is design of the routing protocols which are used to establish and maintain multi-hop routes to allow the data communication between nodes. A considerable amount of research has been done in this area, and many multi-hop routing protocols have been developed. Most of these protocols such as the DSDV [6], Dynamic Source Routing protocol (DSR) [7], Adhoc on-Demand Distance Vector routing protocol (AODV) [8], Temporally Ordered Routing Protocol (TORA) [9], and others establish and maintain routes on the best-effort basis. While this might be sufficient for a certain class of MANET applications, it is not adequate for the support of more demanding applications such as multimedia audio and video. Such applications require the network to provide guarantees on the Quality of Service (QoS).

Some researchers have been active in the area of QoS support in MANETs, and have proposed numerous QoS routing protocols for this environment. Some of these protocols provide QoS support for the link availability for a given path. This is because link availability prediction improves the service of routing protocols. In this thesis, we have discussed link availability between nodes in the networks.

1.4.1 Routing Protocol Strategies

There are three basic Adhoc routing strategies. One is called Table-driven or proactive routing strategy, the second one is source-initiated and is called as demand-driven or reactive strategy. In addition to these two basic methods, third one is hybrid approach that utilizes some of the functionality from both the proactive and reactive strategies. Figure 1.3 depicts this classification.

1.4.1.1 Proactive strategy: In proactive scheme, every node continuously maintains the complete routing information of the network. When a node needs to forward a packet, the route will be readily available; thus there is no delay in searching for a route. However, for a highly dynamic topology, the proactive schemes will spend a significant amount of scarce wireless resource in maintaining the updated routing information correct. Examples of these protocols based on this strategy are Destination Sequenced Distance Vector (DSDV) Routing [6] and Optimized Link State Routing.

1.4.1.2 Reactive strategy: In reactive schemes, nodes only maintain routes to active destinations. A route search is needed for every new destination. Therefore, the communication overhead is reduced at the expense of route setup delay due to route search. These schemes are preferred for the adhoc environment since battery power is conserved both by not sending the advertisements as well as not to receiving them.

1.4.1.3 Hybrid strategy: In hybrid strategies, this protocol divide the network into zones (clusters) and run a proactive protocol within the zone and a reactive approach to perform routing between the different zones. This approach is better suited for large networks where clustering and partitioning of the network is very common.

Abbildung in dieser Leseprobe nicht enthalten

Figure 1.3 categorization of Adhoc routing Protocols

1.4.2 Destination-Sequenced Distance Vector (DSDV)

One of the first routing protocols for MANETs is Destination Sequenced Distance Vector (DSDV) [6], which can be called an adaptation of the Bellman Ford Distance Vector protocol for MANETs. Packets are transmitted between the nodes in the network by using the routing tables which are stored at each node of the network. Each node's routing table lists all available destinations, next hop node and the number of hops to reach there. Each routing table entry is tagged with a sequence number which is generated by the destination node. In AODV, the sequence number serves the purpose of avoiding loops in the route and to indicate their freshness. To maintain the consistency of routing tables in a dynamically varying topology, each node periodically transmits updates in addition to transmitting updates when significantly new information is available. Thus DSDV is a proactive protocol. Route advertisements are sent by broadcast or multicast. In order to reduce the amount of information carried by these advertisements, two types of packets are defined. One carries all the available routing information, and is called “full dump". The other type carries only information changed since the last full dump, and is called the “incremental". Full dumps are transmitted infrequently when no movement of mobile hosts is occurring. When node movements become frequent and the size of the incremental approaches the size of a network protocol data unit (NPDU), then a full dump can be scheduled. To further reduce the traffic, the advertisement of the routes which may not have stabilized yet is delayed. When a mobile host receives new routing information, that information is compared to the information already available from previous routing information packets. Any route with a more recent sequence number is used. Routes with older sequence numbers are discarded. A route with a sequence number equal to an existing route is chosen if it has a better metric such as smaller number of hops. When a link to the next hop of a route is broken, any route through that next hop is immediately assigned an infinite metric and an updated sequence number. The modifications are immediately broadcast in a routing information packet.

1.4.3 Adhoc On-demand Distance Vector (AODV) Routing

Adhoc On-demand Distance Vector (AODV) is the currently most popular routing protocol for MANETs. In this protocol, a node discovers a route on demand, i.e., only when it is needed, and caches it. Network wide flooding is used to discover the routes. This protocol requires that nodes maintain local connectivity information by sending periodic local (1-hop) broadcast messages known as hello messages. Through these hello messages a node becomes aware of its neighbors or nodes in its radio range. When a source node wants to send a message to a destination node and a route to the destination is not available in the cache, it initiates a path discovery process by broadcasting a route request (RREQ) packet. When a node receives a RREQ packet it checks whether it has received the same packet before, if it has then it discards the packet. The node then determines whether it has a route to the destination node in its cache. If it cannot satisfy the route request of the source then it rebroadcasts the packet after setting up a reverse path to the source. To set up a reverse path, a node records the address of the neighbor from which it received the first copy of RREQ as the next hop to the source. Eventually a RREQ arrives at a node (possibly the destination itself) that possesses a current route to the destination. Then node unicasts a route reply (RREP) packet back to the source. As the RREP travels back to the source, each node along the path sets up a forward pointer to the node from which the RREP was received as the next hop to the destination and updates its timeout information for the route entries to the source and destination. Nodes that are not part of the path determined by the RREP, timeout after ACTIVE_ROUTE_TIMEOUT and delete the reverse path to the source.

When a node detects that a destination node is unreachable (a link failure is detected either by failure to receive hello messages or a link-layer acknowledgement), it propagates to all the active neighbors a route error (RERR) packet for the failed routes for which the node was the next hop.

For each route entry a list of active neighbors is also maintained. A neighbor is considered active if it originates or relays at least one packet for that destination within the most recent ACTIVE_TIMEOUT period. All routes in the route table cache are tagged with destination sequence numbers which guarantees that no routing loops can form, even under extreme conditions of out-of-order packet delivery and high node mobility. The sequence number also helps in checking the freshness of a route, the greater the sequence number the more fresh a route is.

Several extensions have been proposed to the basic AODV routing protocol. Some of the most prominent ones have been accepted as part of standard AODV. One such modification is use of link layer feedback to maintain neighborhood information instead of periodic hello messages. Another modification is the use of expanding ring search for route request packets. Instead of sending a network wide broadcast for a RREQ, the source node starts out by sending a limited broadcast (done by setting the TTL (time to live) field in the packet to TTL_START). If this broadcast fails (indicated by a timeout) to find a route to the destination then the source increases the previous TTL value by TTL_INCREMENT and sends out another broadcast with the higher TTL value. This process is repeated till the TTL value reaches TTL_THRESHOLD after which the source sends out a broadcast with TTL equal to NETWORK_DIAMETER. If this broadcast also fails to discover a route to the destination then such broadcasts are sent again upto RREQ_RETRIES. If still a route cannot be found then all the packets queued for that destination are dropped. When RREQ_RETRIES is 0, the timeout for each RREQ is calculated as

Timeout = Min(2.0* TTL * LINK_TRAVERSAL_TIME, MAX_RREQ_TIMEOUT) .

Here LINK_TRAVERSAL_TIME is the time taken to traverse a link and MAX_RREQ_TIMEOUT is the maximum possible value of the timeout. When RREQ_RETRIES is greater than 0 then the timeout of each RREQ is calculated as

Timeout = Min(2.0 * TTL * LINK_TRAVERSAL_TIME * RREQ_RETRIES, MAX_RREQ_TIMEOUT) .

1.4.4 Dynamic Source Routing (DSR)

Dynamic Source Routing (DSR) is another reactive routing protocol and is similar to AODV in operation. The main difference between AODV and DSR is that DSR performs source routing, while AODV uses next-hop information stored in the nodes of the route. Source routing is a routing technique in which the sender of a packet determines the complete sequence of nodes through which to forward the packet; the sender explicitly lists this route in the packet's header, identifying each forwarding hop by the address of the next node to which to transmit the packet on its way to the destination node. The route discovery process in DSR is similar to AODV. When a node wants to send a packet to another host it checks its route cache for a route to the destination. If the route is not available in the cache then the node broadcasts a route request packet containing the identity of the destination. In addition to the address of the source and destination, each request packet contains a route record, which is accumulated record of the sequence of hops taken by the route request packet as it propagates through the adhoc network during route discovery. When a packet reaches at a node that does not contain the route to destination, it appends its address to the route record in the request packet and rebroadcasts the request further. When a packet reaches at a host (including can also be the destination) that has a route to the destination, the host appends the route to the accumulated route record in the packet and sends a route reply. In order to return the route reply packet to the initiator of the route request packet, the node must have a route to the initiator. If it has a route entry for the initiator in its route cache then the route reply packet is unicast to the initiator. Otherwise, the node can reverse the route in the route record of the route request packet, and use this route to send the route reply packet. This, however, requires the wireless links to work equally well in both directions, i.e., the wireless links must be bidirectional. If this condition is not true, then the host can piggyback the route reply packet on a route request packet targeted at the initiator of the original route discovery.

1.4.5 Temporally Ordered Routing Algorithm (TORA)

Temporally Ordered Routing Algorithm (TORA) is a distributed protocol designed to be highly adaptive so that it can operate in a dynamic network. For a given destination, TORA uses a somewhat arbitrary ‘height’ parameter to determine the direction of a link between any two nodes. As a consequence of this multiple routes are often present for a given destination, but none of them are necessarily the shortest route. For a node to initiate a route, it broadcasts a query to its neighbors. This is rebroadcasted through the network until it reaches the destination, or a node that has a route to the destination. This node replies with an update that contains its height with respect to the destination, which is propagated back to the sender. Each node receiving the update sets its own height to one greater than that of the neighbor that sent it. This forms a series of directed links from the sender to the destination in order of decreasing height. When a node discovers link failure, it sets its own height higher than that of its neighbors, and issues an update to that effect reversing the direction of the link between them. If it finds that it has no downstream neighbors, the destination is presumed lost, and it issues a clear packet to remove the invalid links from the rest of the network.

An advantage to TORA is that it supports multiple routes between any source-destination pair. Failure or removal of one node is quickly resolved without source intervention by switching to an alternate route. Unfortunately, there are drawbacks to TORA as well. The most glaring being that it relies on synchronized clocks among nodes in the network. If external time sources are present - (e.g. GPS), it makes the supporting hardware to support it more costly, and introduces a single point of failure if the time source became unavailable. TORA also relies on intermediate lower layers for certain functionality. It assumes, for example, that link status sensing, neighbor discovery, in-order packet delivery, and address resolution are all readily available. The solution is to run the Internet MANET Encapsulation Protocol (IMEP) at the layer immediately below TORA. This makes the overhead for this protocol difficult to separate from that imposed by the required lower layer.

1.5 Cross Layer Design in Wireless Adhoc Networks

The wide spectrum of applications demonstrates that MANETs have some distinct advantages over wired networks, mainly due to their fault-tolerant and self-organizing characteristics. At the same time, mobile adhoc network present a number of complexities and design constraints that are not existent in wired networks. The most important factor characterizing a MANET is the high variability of the network state. We use the term network state to refer to the wide range of communication conditions a node can experience in a MANET. The most important factors characterizing the network state are the link connectivity, the power control and the mobility effect [29].

1. Link Connectivity: In wired network, the link connectivity is a binary value i.e. a link exists between two nodes when they are connected by a physical medium like cable or optical fiber. In a MANET, the broadcast nature of the communication allows each node to be connected with multiple receiver nodes. Mobility of the nodes and small-scale channel variations due to fading, scattering and multipath can change the quality of a link within a few milliseconds. The variable link connectivity increases the number of packets dropped for transmission errors and has direct impact on all the network protocols. The MAC layer may assume that packet drop is caused by collisions and therefore it increases its backoff window. At transport layer, the TCP sender may misinterpret losses as congestion, and may react invoking congestion control and slow start recovery, thus reducing end-to-end performance of the current flow.
2. Power control: The broadcast nature of the wireless communication determines that each node may increase/reduce the number of neighboring nodes by tuning its transmitter power. Thus, the topology of the network as perceived by each node is strongly dependant on the transmit power of each node. Increasing the transmit power also increases the effect of hidden and exposed nodes at the MAC layer and affects the congestion level of the wireless channel. This consumes more energy also, which is of no use.
3. Mobility effect: The nodes in a MANET are free to move and organize themselves arbitrarily. The mobility affects the performance of the network protocols. At the MAC layer mobility factor governs how long the measurements regarding channel state and interference remain valid. At routing layer, the mobility factor governs the performance of the routing protocols. At the transport layer, route failures can be misinterpreted as congestion effects and produce performance decay.

Meeting the requirements of the application despite variable link connectivity, network topology and power levels imply two issues in protocol design:

- Information sharing: Each layer of the protocol stack should be able to access the information about the current network state.;
- Protocol cooperation: Performance gains may be obtained if cross layer/ joint solutions at multiple network layers are considered.

The layered network architecture is well suited for wired networks but it is suboptimal in many applications of MANETs [29, 30, 31] due to variable link connectivity, mobility and power control. The main limitation of the layered model is the lack of cooperation among non-adjacent layers: each layer works in isolation with little information about the network. Moreover, the strict modularity does not allow to design cross-layer/ joint solutions optimized to maximize the overall network performance.

Cross layer design is used to support flexible layer approaches in MANETs [29, 30, 31]. Generally, cross layer design refers to protocol design done by allowing layers to exchange state information in order to obtain performance gains. Protocols use the state information flowing throughout the layered stack to adapt their behavior accordingly. The term state or network state is used to represent the wide range of communication conditions a node can experience in a MANET. For example, given current channel and energy conditions, the physical layer may adapt rate, power and coding to meet application requirements. The cross layer design introduces the advantages of explicit layer dependencies in the protocol stack, to cope with poor performance of wireless links, nodes’ mobility, high error rates, power savings requirements, and Quality of Service.

1.6 Motivation for the Thesis

As we have seen in the earlier section in wireless adhoc networks, it is important to have optimization across the layers in adhoc networks in order to support Quality of Services in MANETs. Cross layer design raises the possibility of improving the performance of mobile adhoc networks. The cross layer optimization focuses on joint solutions involving more than one protocol layers. This motivates the cross layer design as the need for the protocols to be adaptive to network dynamics - mobility and to tackle the constraints i.e. - limited energy.

1.7 Problem definition

In the present work, we investigate and find out solution for cross layer optimization of protocols in mobile adhoc networks in providing service quality. The present work focuses to provide solutions that result in reduced link failures and increased battery life of the nodes by interactions of non-immediate layers. Further, it aims to use link prediction with routing protocol to avoid link breaks at network layer and use of controlled power to transmit control and data packets at MAC layer for power optimization.

1.8 Objectives

The following objectives have been set to achieve the proposed work in the problem definition:

1. Develop a model for link prediction. Incorporating link prediction model developed in the routing information. Use link prediction for advance route discovery. Evaluate the performance of the link prediction model.
2. Modification of the existing power optimization protocol in order to save energy and maximize the network throughput.
3. Propose a cross layer design for power control and link availability in order to improve the performance of mobile adhoc networks. Incorporating link prediction at network layer and power optimization protocol at MAC layer. Evaluate its performance.

1.9 Contributions of the thesis

The contribution of this thesis is cross layer optimization for protocols in mobile adhoc networks to support Quality of Services. This includes cross layer interactions between physical and network layers for link availability and power control at MAC layer.

Most of routing protocols provide best effort service and they are not concerned about quality of service. Mobile Adhoc Networks are characterized by dynamic topology due to nodes’ mobility. Mobility is the main cause of the link failures that affects the services offered by the networks. So in this thesis, we are predicting the availability of the link using Newton divided difference interpolation method.

The battery life of the nodes is also another factor affecting the link availability. Due to limited battery power, once they die out the network connectivity changes. It is also important to optimize the MAC layer to reduce the consumption of power as adhoc nodes have limited battery power. We have proposed dynamic power control protocol for power optimization. Further, cross layer design for the dynamic power control protocol and link prediction (DPCPLP) is proposed that combines the effect of optimum transmit power and received signal strength based link availability using cross layer approach. This method uses optimum transmit power for transmitting the packets to a neighboring node to increase the battery life of adhoc nodes and received signal strength based link prediction to increase the availability of the links.

1.10 Organization of the Thesis

The thesis is organized as follows:

Chapter 1: Introduction: we have explained the basics of wireless adhoc networks, and discussed popular routing protocols used, and many power aware protocols. An overview of cross layer designs overview with their advantages and disadvantages in brief have also been given. In this chapter we have also presented the motivation to pursue the problems in this field.

Chapter 2: Wireless MAC, Routing Protocols and Cross Layer Design: we have explained the related MAC, routing protocols and cross layer designs in depth. We have also explained their advantages and disadvantages.

Chapter 3: Link Prediction Model: we have explained our first novel Link Prediction Model using Newton divided difference method for Mobile Adhoc Networks in detail. We have shown the results and the analysis for Link Prediction model with AODV routing algorithm.

Chapter 4: Dynamic Power Control Wireless MAC Protocol: we have explained our second novel wireless MAC protocol in detail. We have shown the results and the analysis for Dynamic Power Control wireless MAC protocol.

Chapter 5: Cross layer design for Link Availability and Power Control in Mobile Adhoc Networks: we have explained our third novel cross layer design for Link availability and Power Control in detail. We have shown the results and the analysis of cross layer design for link availability and power control.

Finally, chapter 6 concludes the thesis and also gives recommendations for future work.

CHAPTER 2

Wireless MAC, Quality of Service Routing and Cross Layer Protocols

In this chapter, we are going to describe wireless MAC, Quality of Service routing and cross layer protocols for mobile adhoc networks in detail.

2.1 Wireless MAC Protocols

In this section, two wireless MAC protocols are discussed. These are IEEE 802.11b Std. and Minimum Transmit Power Control wireless MAC protocols for Mobile Adhoc Networks.

2.1.1 IEEE 802.11b Std.

IEEE 802.11b Std. supports three modes of wifi MAC protocol ─ i) Distributed Coordination Function (DCF), ii) Point Coordination (PCF) and iii) Hybrid Coordination Function (HCF). Out of these three we are considering only Distribution Coordination Function. In DCF, there are two schemes of MAC protocols. One is Basic Access scheme and other is the scheme with Virtual carrier sensing using RTS-CTS handshake. The basic access Scheme doesn’t make use of RTS-CTS packets. Hence there will be collisions of DATA packets. It take into account the hidden terminal problem. So the collisions of DATA packets in case of Basic Access Scheme are far more in the scheme with virtual carrier sensing using RTS-CTS handshake. Further, the RTS-CTS based scheme is described in detail.

Before we move on to the description of the RTS-CTS scheme we first have to understand the different types of Inter Frame Spacing (IFS) defined in the IEEE 802.11b Std. An IFS is the time interval between the packets or frames. The carrier sense mechanism at the Physical layer gives the information about the channel condition to the MAC layer at every time instant. A station or a node will be able to determine the idle channel and the instant when to transmit by studying the interval for which the channel is idle and comparing it with various IFS. Five different IFS are defined to provide priority levels for access to the wireless media. These are as follows:

- SIFS (Short Inter Frame Spacing)
- PIFS (PCF Inter Frame Spacing used only in point Coordination Function)
- DIFS (DCF Inter Frame Spacing)
- AIFS (Arbitration Inter Frame Spacing used by the QoS facility)
- EIFS (Extended Inter Frame Spacing)

Out of these five IFS, we will describe three types of IFS (SIFS, DIFS and EIFS) as PIFS is used only in Point Coordination Function and AIFS is used for the QoS implementations.

SIFS (Short Inter Frame Spacing)

The SIFS is the time which should elapse after end of the last symbol of the previous frame, before subsequent frame can be transmitted by any node. The nodes wait for SIFS prior to transmission of an ACK, CTS frame or the DATA packets. The SIFS frame is the shortest duration (spacing) between two consecutive frames. Duration of the SIFS is 10 microseconds.

DIFS (DCF Inter Frame Spacing)

The DIFS is used by stations/nodes operating under the DCF to transmit data frames. A station using the DCF shall be allowed to transmit if its carrier sensing (CS) mechanism determines that the medium is idle for DIFS period after a correctly received frame, and its back-off time has expired. DIFS is an interval between end of one successful communication and start of the contention for the next DATA transmission.

EIFS (Extended Inter Frame Spacing)

When a node receives an erroneous packet (collided packets or packet with bursty errors) it doesn’t contend for the EIFS duration. EIFS duration is 200 microseconds. It is usually used by nodes when they fall in carrier sensing region and not in the transmission region. In the carrier sensing region they can just detect a packet and not decode it successfully. So the node treats the packet as noise and keeps quite for EIFS duration.

2.1.2 RTS-CTS-DATA-ACK four way handshake MAC protocol

The figure 2.1 gives a description about how the MAC protocol works. When a node has a packet to send, it first sends an RTS packet. The RTS packet contains the source MAC address, destination MAC address and NAV (Network Allocation Vector). NAV field contains the time interval for which the complete communication would continue. When the desired destination node receives this packet, it first confirms that the RTS is meant for it by comparing the destination MAC address. If this node is ready to receive packet from the sender, then it sends back the CTS packet. CTS packet contains the destination MAC address and NAV.

The receiver node calculates the remaining time from the NAV which it observes from RTS packet and inserts it in the CTS packet. After sending RTS packet the sender waits for SIFS period of time to receive CTS packet. If it starts receiving the CTS packet within that time then after it receives CTS it starts sending DATA packet after SIFS interval. Once the DATA is received correctly by the receiver, it starts sending the ACK packet after SIFS interval. ACK packet contains only the destination MAC address. Once the ACK packet is received by the sender, send by the receiver, it assumes the DATA transfer to be successful.

Abbildung in dieser Leseprobe nicht enthalten

Figure 2.1: RTS-CTS-DATA-ACK four way handshake MAC Protocol

In this four way handshake MAC protocol a concept of virtual sensing is used. RTS packet contains the duration for which the communication is going to last. This duration contains SIFS + CTS + SIFS + DATA + SIFS + ACK time. Whenever a node receives RTS packet which is not meant for it, it sets its NAV to the NAV contained in the RTS packet. This means that even if the node senses the channel to be idle, still it won’t transmit packet until and unless the NAV is not zero. This node also sets another time out. This time out is equal to SIFS + CTS + SIFS + Turnaround time. If it doesn’t receive the start of the data within the time interval then it assumes that the RTS-CTS handshake wasn’t successful and hence it resets the NAV which it had set earlier. When a node receives a CTS packet which is not meant for it, it checks the NAV value contained in the CTS packet. It sets its NAV value to the NAV in the CTS packet. Hence the node will defer to access the channel for the NAV period according to the virtual carrier sense mechanism. Once the NAV of each nodes becomes zero as it is decremented with time, every node will defer to access the channel for DIFS period. If the nodes do not receive anything within that period then they will start contending for the channel, otherwise they will wait for the channel to become idle again.

Backoff Mechanism

If a node wants to transfer DATA packet then it checks whether the channel is idle or busy through carrier sensing. If the medium is busy, the STA shall defer until the medium is determined to be idle without interruption for a period of time equal to DIFS when the last frame detected on the medium was received correctly, or after the medium is determined to be idle without the interruption for a time equal to EIFS when the last frame detected on the medium was not received correctly. After this DIFS and EIFS medium idle time, the STA shall then generate a random backoff period for an additional deferral time before transmitting, unless the backoff timer already contains a nonzero value, in which case the selection of a random number is not needed and not performed.

Backoff Time = Random () x Slot Time (2.1)

Random () is a Pseudo random integer drawn from a uniform distribution over the interval [0, CW], where CW is the contention window CWmin ≤ CW ≤ CWmax. CWmin is 32 and CWmax is 1024 for DSSS. Slot time depends upon physical layer but is 20 microseconds for DSSS. CW is first initialized to CWmin. After every unsuccessful transmission, the CW is double until it becomes CWmax after which it is not increases. After 10 transmissions the packet is discarded as corresponding message is send to the higher layer. If some other node starts transmitting packets before the node’s backoff counter becomes zero then the node freezes the backoff counter and decrements only after it starts sensing the channel.

2.1.3 Minimum transmit Power Control MAC Protocol

Unlike in IEEE 802.11b Std MAC protocol, in these schemes the transmission power is not kept constant. Every node transmits at different power to different neighbors. The packets are transmitted in such a way that transmission power is less and still the receiver is able to receive the packet correctly. So in these protocols, the authors have tried to reduce the power consumption of the node by making the node transmit the packets at least power. The authors have made changes in field of CTS and DATA packets to include some more information about the power control. The basic concept of these protocols is that every node tries to transmit packet at minimum power level required to reach the destination node. The two minimum power control protocols are Adaptive Power Control MAC Protocol for Adhoc Networks [24] and Distributed Power Control in Adhoc networks [25]. These protocols are similar to each other, difference being that adaptive power control uses Open loop power control whereas distributed power control uses closed loop power control to find out the minimum power level required so that the destination node is able to decode the packet successfully. We will describe Adaptive power control protocol after distributed power control protocol.

[...]