Zhao Li

(Department of Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China)

Abstract：The application environments of wireless Ad hoc networks require that it should support Quality of Service(QoS).However,that is very difficult because of the inherent characteristics of the wireless channel and the frequent changes of network topology caused by nodes movement.An Ad hoc QoS Multicasting(AQM)protocol can solve this problem by previously reserving the neighbor nodes for tracking resource availability.By considering QoS restrictions of transport delay,loss ratio,bandwidth requirement,delay jitter,and throughout,and by finding the adaptive routing,the AQM protocol can obviously improve the efficiency of multicastsession.The results of network simulation show that QoS is essentially applicable to Ad hoc networks.

W ith the emergence of services that have strict Quality of Service(QoS)requirements,such as real-time multimedia service,interactive service,and more,the modern networks are required to provide specific QoS guarantees.Ad hoc networks have the same requirements on QoSguarantee.Therefore,supporting QoSguarantee is the key technology for Ad hoc communications to find a practical application,as well as for wireless Internet to deliver multimedia real-time services.

QoSrouting plays an important role in QoSguarantee implementation.It is necessary to select an appropriate path between the source node and the destination node before setting up a connection and reserving resources.On one hand,the path selection is restricted by available resources in the network,but on the other hand it must meet certain QoS requirements such as the requirements on end-to-end bandwidth and delay.

Multicast is a point-to-multipoint or multipoint-to-multipoint communication,in which many receivers imultaneously receive the same information sent by one source.In a multicast session,a multicast group is formed by a collection of all sending and receiving nodes.

Generally,multicast applications include conference call,Video on Demand(VOD),interactive network games,and more,which are certain network applications based on groups or protocols.As efficiency of multicast technology and unique advantages of Ad hoc networks can be favorably combined,there will be a promising prospect to develop group-based multicast applications in Ad hoc networks.Nowadays,multicast routing protocols for Ad hoc networks become a hot topic in the research field of wireless communications.

1 Existing Multicast Routing Protocols

These protocols support multicast routing,and the core for them is to manage multicast group members,dynamically create and maintain a multicast transmission structure,and set up the transmission routing for multicast data.

As Ad hoc network topology undergoes frequent changes,the QoSrouting issue becomes quite complex.Assuming that Ad hoc network topology changes so slowly that status information about the topology change in a certain interval can be updated,the Ad hoc network is considered stable.Most of the current QoSrouting and related algorithms are based on the assumption that the Ad hoc network is stable.Several multicast routing protocols have been introduced for Ad hoc networks.

1.1 ODMRP

On-Demand Multicast Routing Protocol(ODMRP)is a multicast routing protocol designed for Ad hoc networks,with which senders of multicast data set up multicast routings on demand[1].ODMRPcreates a multicast mesh connected with the sender and the receiver to forward multicast data packets.Asource sending node can periodically update the membership and routing information.

When joining or leaving a multicast group,a node needn't send extra control information,nor rely on the underlying unicast routing protocol.

ODMRPis a simple and robust protocol.However,its weakness is that when there are many sending nodes in a multicast group,flooding of control messages would result in too many channel overheads.

1.2 MAODV Routing Protocol

Multicast Ad hoc On-demand Distance Vector(MAODV)routing protocol is derived from unicast Ad hoc On-Demand Distance Vector(AODV)[2].In MAODV,a node wishing to join a certain multicast group to receive or send data shall originate the process for setting up a multicast routing.Routing Request(RREQ)and Routing Response(RREP)messages are used in AODVfor setting up the multicast routing,while an additional Multicast Activation(MACT)message is also used to confirm the routing.MAODVdynamically creates a shared multicast tree to transfer multicast data packets.Anode shallsend certain control information when joining or leaving a multicast group and maintain the related multicast tree.

The MAODVrouting protocol is not completely scalable or robust,although it is easy to be implemented upon AODV.

1.3 CAMP

Core Assisted Mesh Protocol(CAMP)is a mesh-based Ad hoc multicast routing protocol[3].It sets up a shared multicast mesh containing the reverse shortest path from all receiving nodes to sending nodes for each multicast group.There are one or many core nodes in CAMP.Instead of using the“flooding”method,other nodes send to the core nodes the requests for joining a multicast group,thus saving communication overhead.The failure of core nodes does not stop packet forwarding or the process of maintaining the multicast meshes.CAMPallows the sending node to join the multicast group in a simplex mode,that is,only to send multicast data without receiving data sent by other nodes in the group.CAMPrelies on an underlying unicast routing protocol,which guarantees correct routings and distances to all destination nodes within a finite time.

CAMPuses core nodes to avoid flooding of control messages when other nodes join the multicast group.However,with node failure and network segmentation,CAMPhas to rely on the underlying unicast routing protocol to work normally.

1.4 AMRoute

Ad hoc Multicast Routing(AMRoute)protocol creates a bidirectional and shared virtual multicast tree for each multicast group.It uses only multicast data senders and receivers as tree nodes and only group members to reproduce and forward multicast packets.In addition,it doesn't need to be supported by other unrelated network nodes[4].It is necessary to create a multicast mesh for connection of group members before the multicast tree is created.

AMRoute concerns robustness of the multicast routings other than minimum bandwidth or time delay.Moreover,it needs to rely on the underlying unicast protocolto handle dynamic network topology changes.

1.5 AMRIS

Ad hoc Multicast Routing Protocol utilizing Increasing ID numbers(AMRIS)[5]is an on-demand multicast routing protocol based on the shared tree that supports many senders and receivers in a multicast session.The core of AMRISis to take certain a sending node in the session as the tree root,dynamically assign a Multicast Session Member Identifier(MSM_ID)to each node to form a directed acyclic graph,and finally use the subset of directed acyclic graphs to form a multicast tree.(The further the node is from the root,the larger its MSM_ID value is.)The MSM_ID can be used to dynamically manage a node's joining or leaving a multicast group.Furthermore,it determines the transfer direction of multicast data and reconstructs the multicast tree when the path is interrupted,and prevents creating the multicast tree loop.

In AMRIS,a node doesn't need to store overall information.Although only partial path shall be recovered,many control overheads are still needed for maintaining MSM_ID,especially when the network topology frequently changes.

2 AQM Routing Protocol

The multicast routing protocols mentioned above are primarily designed to transfer multicast data with minimum redundancy to each member of the multicast group and guarantee rerouting when the routings undergo changes.However,they have little concern about issues of transmission delay,delay jitter,and bandwidth.

With the development of networks and the continuous growth of user requirements,some special services require both basic communication guarantee and network delay and bandwidth guarantee.Therefore,the major concern for Ad hoc networks is how to make good use of resources,improve data transmission efficiency,and provide QoSguarantees for multimedia services.

Under this background,the design for multicast routing shall take into account the QoSindices such as transmission delay,loss ratio,bandwidth requirement,delay jitter,throughout,and more;routings that meet the specific QoSrequirement can accordingly be found.Based on this principle,the structure of Ad hoc QoSMulticast(AQM)protocol[6]is made up of 3 functional modules including session initiation and destruction,membership management,and neighborhood management.

2.1 Session Initiation and Destruction

A session can be started by any node,which broadcasts a session initiation message(SES_INIT)consisting of the node ID,the application type of the session,and parameters required for QoSguarantees.In the network,each node participating in the session has a session table(TBL_SESSION)to store the session information.

▲Figure 1. Simulation result of high-quality voice service.

A membership table(TBL_MEMBER)can be used to record the status of the predecessor(previous hop)and the QoS information of the path from the source node to the local node via this predecessor.Before the packet is forwarded and rebroadcasted,each node shallfirstly update its QoSfields according to the current network conditions.The packet will be dropped if QoSrequirements can not be met any more.the TBL-MEMBER,hop count information is used to prevent loop formation.

The session is closed by its initiator with a session destruction message(SET_DESTROY).Upon receiving it,a node will clean all data of its tables related to this session or release the occupied channel to stop the transmission if it is currently forwarding the session data.Thus,all nodes that receive the session destruction message are forced to leave the session.

2.2 Member Nodes Management

A node shall firstly broadcast a join request message(JOIN_REQ)if it wants to join a session.The JOIN_REQ message is replied only by members of the destination multicast group.Upon receiving the JOIN_REQ,a member of the destination multicast group modifies the related route table and multicast table,and unicasts a join reply message(JOIN_REP)that contains the address of next hop and QoSinformation of the path.

After waiting for a while,the node sending the JOIN_REQ will receive many reply messages.It selects the node with the best QoSguarantees among severalreplies it receives,and unicasts a join reserve message(JOIN_RES)to the successor(next hop)it has selected.Upon receiving the JOIN_REQ,the successor updates its multicast table.If the successor is not a previous member of the multicast tree,it will also unicast a JOIN_RESto the successor(next hop)of its own multicast table.The JOIN_RESis unicasted through one hop to another until arriving at the node sending the JOIN_REP.In this way an updated multicast tree is created.

Anode shall send a leave session message(LEAVE_SES)if it wants to leave the multicast tree.When its neighbors receive the LEAVE_SES,they will delete its information from their multicast routing tables without having to return a reply message.

2.3 Neighbor Nodes Management

Each node periodically broadcasts hello messages(NBR_HELLO)informing its neighbors of its existence and bandwidth usage.Each node stores the received NBR_HELLO messages in its neighborhood table(TBL_NEIGHBOR).The information in this table is used to calculate the total bandwidth allocated by the neighboring nodes to multicast sessions.If a node doesn't receive any NBR_HELLO from a neighbor for a while,it considers that neighbor lost.The lost neighbor is deleted from TBL_NEIGHBOR,TBL_SESSION,and TBL_MEMBER.

Due to the broadcasting nature of the wireless network,the available bandwidth of a node is the residual capacity in its neighborhood.Anode can only use the remaining resource not used by itself and its neighbors.This approach to residual bandwidth calculation has some errors since it does not consider bandwidth usage beyond direct neighbors.Thus,there will be hidden terminals.

3 Simulation of AQM Routing Protocol

The article[6]provides a simulation of the AQM routing protocol.The simulation is conducted for two types of services:high-quality voice service and high-quality video service.The two services have different QoSrequirements.High-quality voice service requires a transfer rate of 128 kb/s and a delay of less than 10 ms,while high-quality video service requires a transfer rate of 256 kb/s and a delay of less than 100 ms.The simulation results are shown in Figure 1 and Figure 2 respectively.

▲Figure 2. Simulation result of high-quality video service.

In Figure 1,there is no significant difference between the two calculation results for small networks of less than 15 nodes due to the small amount of bandwidth required by high-quality voice service.As the network size grows,however,AQM supports more sessions.In a 50-node network,the session satisfaction grade is down to 75%for AQM,and around 50%for the non-QoSscheme.In the simulation for high-quality video service,when AQM is adopted,the session satisfaction grade is above 60%in a small network of less than 30 nodes.As the network size grows,the session satisfaction grade will gradually decrease to about 25%.On the other hand,for the non-QoSscheme,in a network of more than 30 nodes the session satisfaction grade drops rapidly to about 20%.The two simulation results show AQM has distinct advantages over the non-QoSscheme in network performance.As the network grows in size,their difference will become more and more obvious.

4 Conclusions

The AQM protocol improves significantly the multicast efficiency by tracking the availability of resources based on reservations made previously and announces the QoSconditions at session initiation.When nodes join a session with certain QoS requirements,this information is updated and used to select the most appropriate routes.

AQM is a relatively simple QoSmulticast routing protocol that doesn't involve issues of reliability,scalability,and security.These issues will be the trends for future study on multicast routing protocol.