Multicasting with Quality of Service in Mobile Ad hoc Networks
ABSTRACT
Recently, multimedia and group-oriented computing become increasingly popular for the users of wireless mobile networks. Quality of service (QoS) issues has initiated to be studied in Mobile Ad hoc NETworks (MANETs) to support multimedia and real-time applications. MANETs can provide users with the mobility they demand, if efficient QoS multicasting strategies are to be developed. In this paper, we study the QoS requirements with multicast routing in ad hoc networks and propose a new cross-layer framework which provides QoS guarantees to multicast routing in MANETs. We propose a multicast routing protocol with mechanisms to ensure QoS guarantees to multicast session (call-admission, bandwidth reservation and delay constrain). The proposed routing protocol uses forward group to apply multicast routing with QoS from source(s) to a group of destinations.
KEYWORDS :
Ad hoc networks, MANETs, Quality of service, multicast and admission control.
In MANETs, all communications are done over wireless media, typically by radio packet through the air, without the help of wired base stations. Direct communication is allowed only between
adjacent nodes, so distant nodes communicate over multiple hops, and nodes must cooperate with each other to provide routing.
The QoS routing in MANETs is difficult because the network topology may change constantly, the available state information for routing changes dynamically, nodes may join, leave, and rejoin an ad hoc network at any time and any location. Additional challenges in ad hoc networks are attributed to mobility of intermediate nodes, absence of routing infrastructure, low bandwidth and computational capacity of the nodes. Another challenge with supporting QoS for real-time applications is associated with the design of the medium access control (MAC) protocol. The dynamic nature of wireless ad hoc networks makes it difficult to dynamically assigning a central controller to maintain connection state and reservations. Because of this, best effort distributed MAC controllers are widely used in existing wireless ad hoc networks.
There are many requirements to provide QoS in MANETs, first, find a route through the network that is capable of supporting a requested level of QoS. Second, ensure that when network topology changes, new routes that can support existing QoS are available or can be quickly found. Third, respond to changes in available resources, either as the result of a route change or as the result of change link’s characteristics with a given route.
QoS in MANETs is highly dependent upon routing and medium access control [5], also there is a strong coupling between routing and MAC layer to improve QoS in MANETs [6]. Delivering end-to-end service quality in MANETs is intrinsically linked to the performance of the routing protocol because new routes or alternative routes between source destination pairs need to be periodically computed during ongoing sessions [7].
Protocol layering is an important abstraction that reduces complexity for designing network but it is not well suited to wireless networks because the nature of the wireless medium makes it difficult to decouple the layers. Without interaction between protocol layers, meeting the end-to-end performance requirements of demanding applications will be very difficult. Stringent performance requirements to provide QoS multicast applications over MANETs can only be met through a cross-layer design. Information exchanged between layers ensures robustness. For example, routing protocols can avoid building routes that cannot meet QoS requirements depending on information that come from MAC layer.
In many previous studies that proposed for unicast routing with QoS, a CDMA/TDMA channel model was used in MAC layer [1][2][3][4]. A CDMA/TDMA can be used as MAC protocol in single hop wireless network; however, it is not acceptable in multi-hop ad hoc networks. It is difficult to realize such centralized MAC scheme in a dynamic wireless environment, where the IEEE 802.11 is widely used [8]. In addition, CDMA/TDMA is difficult to be implemented in a real network due to issues of code and time synchronization between nodes [9]. Applying highly synchronized solutions in MANETs is expensive and synchronization can fail when nodes are mobile. Re-assignment of slots after topology changes makes a legacy TDMA scheme very inefficient [10].
Because the wireless medium of a node is shared among neighboring nodes, we must not only take into account the transmission of the node but also consider the transmission of all the node’s neighbors in determining a node’s effective available bandwidth capacity. To measure the available bandwidth we will use the same method that was used in [11], they propose to compute available bandwidth based on the channel status of the radio to determine the busy and idle periods of share wireless media.
The design of QoS-aware protocols under these challenges is non-trivial and requires coordination between different layers of the protocol stack, so we propose a cross-layer framework to provide QoS multicast in MANETs.
Multicast routing is a promising technique, that packets are only multiplexed when it is necessary to reach two or more receivers on disjoint paths. Due to the increasing popularity of multimedia applications and potential commercial usages of MANETs, it is a logical step to support QoS in the multicasting. There are many applications, which naturally require QoS support in the multicasting scenario. In a video/audio conference, the chairmen with other attendees make up a multicast group. Yet, many multimedia applications are characterized by a multicast communication pattern.
Several protocols have been developed to perform ad hoc multicast routing, i.e. CAMP, FGMP, ODMRP, and SOM. However, these multicast protocols did not address the QoS aspect of ad hoc communication. There are several studies for unicast routing protocols with QoS in MANETs in literature [1][2][3], but QoS support for a multicast protocol should be differently designed from the unicast QoS. For a unicast QoS, the main issue is related to the resource reservation between a source and a destination. On the other hand, a multicast QoS should provide QoS paths to all destinations, not only between the source and destination; as a result, QoS multicast should cope with large number of receivers and be able to utilize them.
[4] addresses QoS multicast routing, this protocol uses a lantern-tree as a topology for multicast group and CDMA/TDMA model at MAC layer; lantern-tree takes long time at startup to find all paths and to share time slots between neighbors. It splits flow in to multiple paths which add more complexity when more than one flow are admitted, nodes need to store and process more information about sub flows, multiple paths built and released without sending through them. In addition, CDMA/TDMA is difficult to be implemented in a real network as we discussed previously and mentioned in [8][9][10].
This paper is structured as follows: section2 introduces the cross–layer framework and conclusions in section 3.
2. Multicast routing with QoS
We propose a routing protocol that uses forward group to apply multicast routing with QoS from source(s) to a group of destinations. In the proposed protocol, we will try to take all limitations of MANETs into account and provides a general cross-layer framework for implementation of QoS.
2.1. Session initiation and destruction
A node that has data to send starts session by broadcasting a session initiation as a quality of service route request (QRReq) with Time-To- Live (TTL) greater than zero. Intermediate nodes rebroadcast QRReq if they have available bandwidth until arriving at destinations or TTL equal zero. Destination nodes receive QRReq and send route reply (RRep) to the source. Source nodes and destination nodes can leave the session by not sending QRReq and RRep respectively.
2.2. Forward group and member management
When an intermediate node receives QRReq from source node, it stores the source ID and the sequence number in its message cache to detect any potential duplicates. If the message is not a duplicate, intermediate node has available bandwidth and the TTL is greater than zero, then the node rebroadcast QRReq; routing table is updated with node ID that receives from it. The destination node will receive QRReq from several paths; it selects one path with the best QoS conditions and sends route reply (RRep). When an intermediate node receives RRep from destinations, it checks if the node ID in RRep matches its own ID. If it does, the node realizes that it is on the reverse path to the source and it is a part of the forwarding group, so it sets the forwarding group flag. The next hop node ID field is filled by extracting information from its routing table. In this way, each intermediate node propagates the RRep until it reaches the multicast source via the selected path. This whole process constructs or updates the routes from sources to receivers. Through this process, all paths to destinations will be defined and source node can start sending data packet.
2.3. Admission control
We use distributed admission control at every intermediate nodes, when intermediate node receive QRReq packet, it must calculate its available bandwidth and rebroadcast QRReq packet if it has available bandwidth. QRReq forwarded as long as QoS requirements are met. The packet is dropped if QoS requirements cannot be met any more, avoiding flooding the network unnecessarily. Before QRReq packet rebroadcast, each intermediate node temporarily updates its QoS information with the current QoS conditions. With this rule, nodes do not accept more traffic than the bandwidth available. Figure1 shows structure of route request with QoS requirement phase and figure2 shows reply phase and forward group establishment. In our framework, we propose to compute the available bandwidth based on the channel status of the radio to determine the busy and idle periods of the share wireless media. By examining the channel usage of a node, we are able to take into account the activities of both the node itself and its surrounding neighbors and therefore obtain a good approximation of the bandwidth usage; we will use the standard IEEE 802.11 at MAC layer.
2.4. Bandwidth reservation
In [4], CDMA/TDMA protocol used at MAC layer, every node in the path needs to share information with all neighbors about free slots. In our scheme, we propose to use a distributed bandwidth reservation, where each intermediate node in the network will calculate its own available bandwidth independently without need to share information free time slots with neighbors. Intermediate node rebroadcast data packet if it is a forward node for the source of data packet, Figure3 shows forward data packet phase.
The available bandwidth calculation will be used by our call admission control to determine if QRReq can be accepted. Using call admission control at intermediate nodes prevents false admission control that appear as a result of multiple sources simultaneously initiating admission control at the same instance and sharing common paths and nodes between source-destination pairs. In a non-QoS scheme, intermediate nodes do not check their bandwidth requirements before rebroadcast RReq packet. Because of this, some of forwarding nodes become heavily overloaded. As a number of senders grow, more than one RReq are accepted without considering the available bandwidth.
2.5. Use multi forward group for Load balancing
The new idea is using many numbers of forward groups to apply multicast with QoS and balance the overload. Considering the QoS support, the bandwidth on a single link might not be adequate if there are many sources in the network and consequently, many packets may be discarded, so we propose a practical situation that the data packets from different sources may come from different directions to a local group. When intermediate node drops QRReq, it will arrive at destinations through other nodes that have enough available bandwidth. In addition, load balancing appears through updating forward group.
2.6. Route recovery and prevent congestion
Most multicast applications belong to category that number of senders is less than number of receivers. In this situation, sender advertising is more efficient than receiver advertising [5], so in our proposed routing protocol we use sender advertising. Each source periodically sends QRReq that make route recovery by updating forward group.
The problem with the admission control solution in most previous studies is that a one-time procedure performed before the flows starts. It does not take into account the change in the wireless network over the duration of the flow’s operation. Capacity of channel may change dramatically and available bandwidth that estimated by individual nodes will be change with dynamic mobility of nodes (move to each others) and due to fading and out side interference [12].
In our approach when source update forward group, paths will update also and nodes reestimate the available bandwidth, so all changes that appear as a result of node movement will be taken.
Any forward node can detect congestion using periodic traffic measurement. When a node detects such congestion, it starts sending a prop packet to source or destination. If it sends to source to update forward group, overhead will be high because of control packet. If it sends to destination node, destination nodes need to process and save all alternative paths when route request are received. In addition, destination nodes measure packet delay, if a packet takes long delay; destination node drops it and sends update to source.
2.7. Structure of framework
Figure1 shows QoS route request phase from source to destinations and describes how intermediate node behaves when it receives QoS route request.
Figure2 shows route reply phase from destinations to source, describes how intermediate node behaves when it receives route reply and when it sets to be a forward node.
Figure3 shows data packet phase from source to destinations, describes how intermediate node behaves when it receives data packet.
Figure4 gives an overview about cross layer (interaction between network, routing and MAC layers) and action performs at intermediate node. Describes how intermediate node checks QoS requirements and estimates available bandwidth depending on information that come from MAC layer
3. Conclusion & future work
In our scheme, number of forward group will go up or down depending on: number of sources, number of receivers and statues of network. When the network bandwidth is strictly limited, the number of forward group will be large, whereas the network bandwidth is sufficient, the number of forward group will be small. Number of destination nodes will be limited if there is no intermediate nodes forward to them. Through updating forward nodes, congestion will prevent and unnecessary reservation will be free. We use distributed admission control at every intermediate node, so there is no need for interaction between nodes, also admission control prevents new destinations to join multicast group if there are no QoS requirements. This is a proposed solution based on a preliminary analysis of the problem, as for future work, we plan to do research on performance analysis.
References
[1] Y.-S. Chen et al. “On-demand, link state, multi-path QoS routing in a wireless mobile ad-hoc network". European Wireless. 2002.
[2] C.-R. Lin. “On-demand QoS routing in multi-hop mobile networks”. Proceedings of the IEEE INFOCOM. 2001. 1735–1744.
[3] Y. Chen and Y. Yu. “Spiral-Multi-Path QoS Routing Protocol in a Wireless Mobile Ad- Hoc Network”. IEICE Transactions on Communications. 2004. 87-B(1). 104-116.
[4] Y. Chen and Y. Ko. “A lantern-tree based QoS on demand multicast protocol for a wireless ad hoc networks”. IEICE Trans. Communication. 2004.
[5] L. Mohammed. “Ad hoc wireless networks”. CRC. 2003.
[6] H. Zhu et al. “A survey of Quality of Service in IEEE 802.11 Networks”. IEEE Wireless Communications. 2004. 11(4). 6- 14.
[7] S. Lee et al. “INSIGNIA: An IP-Based Quality of Service Framework for Mobile ad Hoc Networks”. Journal of Parallel and Distributed Computing. 2000. 60. 374-406.
[8] K. Xu et al. “Adaptive Bandwidth Management and QoS Provisioning in Large Scale Ad Hoc networks". Scalable Network Technologies, CECOM RDEC STCD. MILCOM. 2003.
[9] R. Gupta et al. "Interference-Aware QoS Routing for Ad-Hoc Networks". ICC. 2005.
[10] I. Chlamtac et al. “Mobile ad hoc networking: imperatives and challenges”. Ad Hoc Networks Publication. 2003. 1(1).
[11] Xu Kaixin et al. “Adaptive Bandwidth Management and QoS Provisioning in Large Scale Ad Hoc Networks. Proceedings of MILCOM. Boston. 2003.
[12] Yaling Yang and Kravets R. “Distributed QoS guarantees for real-time traffic in ad hoc networks” Sensor and Ad Hoc Communications and Networks. 2004
