"Without accepting the fact that everything changes we cannot find the perfect composure. But unfortunately, although it is true, it is difficult for us to accept it. Because we cannot accept the truth of transience, we suffer" -- Shunryu Suzuki

THINK about these HOME LEARN about me TASTE these links SEE my pictures SIGN / VIEW my guestbook     Last Update : Oct 09, 2005  My Research Work  Bluetooth  MSP430  Free Space Optics  Communication Systems  Electrical Engg.  Ericsson BT Modules  Linear Prediction  Multi-user Detection    Wireless Channel Model

AD-HOC NETWORKS                                                                                                       QoS Issues in MANets
                                                                                                                             A new Cluster-Based Routing Approach
    

Related:  On the motivation behind clustering protocols in Ad-Hoc networks (A Mathematical Analysis) [Report] Presentation]

The traditional notion of a wireless network is one in which there are a few Base Stations or Access Points (BS or AS) and a number of Mobile Stations or Nodes (MS). Each MS communicates directly to the BS which is closest to it and exchanges data. This divides the entire geographical area into "cells" (hence the name 'cellular') which are served by one BS each. All the BSs are in turn connected through high speed backbone links so as to allow calls from one cell to another. Thus, the network topology is a "distributed star" sort of picture with BSs being the local hotspots. Such a scenario requires a lot of infrastrtucture and hence needs time and money to set up and once set up, removing the infrastructure will also not be sensible.

On the other hand Ad-Hoc Networks, as the name implies, are "meant to be" temporary in nature. The idea is to elminate the BS completely. Imagine a scenario in a disaster relief operation wherein timely communication is a very important factor, the relief workers come in the area and without the need of any existing infrastructure, just switch on their handsets and start communicating with each other while moving and carrying out rescue work!

So, here we have a set of nodes which are completely independent of each other and one needs to find out ways to allow them to communicate amongst themselves.Supposing, Node A wants to send data to Node B. Then exactly one of the following is possible:

1. Node A and B are in the transmission range of each other and hence can talk directly. In this case, A sends the data directly to B.
2. A and B cannot hear each other directly. In this case, A needs to find a path via other neighbouring nodes to B. The path finding algorithm should be fast and should lead to minimum overhead in terms of control and signalling packets to be exchanged. This is known as Multi-Hopping.

Hence, packets need to be routed through multi-hopping most of the time and this calls for "efficient" and more reliable ways of finding paths in the network. There are various issues to be considered in Ad-Hoc Networks:

• Routing packets in such a setup is not easy and algorithms need to take care of the following aspects:
  • An intermediate node may move away in the middle of data transfer and hence a new path will have to be recomputed.
  • In case the requesting application desires certain Quality of Service guarantees, one should have a mechanism of providing the same. QoS in Ad-Hoc Networks is a research area in itself.
    
    
• Power Management is an important issue. Since, all nodes in an Ad-Hoc Network are allowed to be mobile, they will suffer from severe power constraints. So, managing the power resources and optimal strategies for sleeping etc. need to be worked out.
  
  
• Selfish Nodes. Since, power is at a premium, some nodes may become selfish and refuse to route packets of other nodes thereby severely hampering the performance of the network. Stringent norms and measures need to be put into place to prevent such situations. e.g. other nodes may also refuse to route packets of the selfish node etc.

I have worked on Quality of Service Issues in MANets and proposed a new clusterhead-less clustering algorithm for QoS routing in MANets. I am currently studying the performance of the algorithm. The report is here

Quality of Service (QoS) in Mobile Ad-hoc NETworks (MANets) 

Introduction to QoS
Quality of Service (QoS) is a measure of the level of service that a particular data gets in the network. Two packets A and B may not be given the same service (i.e. some packets will be treated as Very Important Packets (VIPs) and some others as VVIPs and will be given `assured' service). The basic idea behind `assured' service is to differentiate between traffic coming into the network and provide preferential treatment to some types of data i.e. one is looking for prioritizing traffc.

QoS can be measured in terms of parameters like data rate, delay, delay variation (jitter), packet loss etc. Providing QoS in MANets has its own challenges and problems. Some of the difficulties faced are :

• Varying Physical Link Properties: Since the wireless link is unpredictable and time varying, it becomes difficult to ensure that a minimum level of service is satisfed.
  
  
• Medium Access Issues: Since the wireless channel is shared by many devices, managing them in such a way that the QoS guarantees are fulfilled is difficult.
  
  
• Routing: Since the nodes are mobile, hence the network topology changes randomly with time and hence the routing protocol needs to update the routes and links.
  
  
• Power consumption: Nodes being mobile, have a limited power capacity.
  
  
• Characterisation of the Link state: Since the network state changes with time, one needs to have some mechanism in place which can continue to update the network state and based on it predict whether it will be able to achieve a particular quality of service requirement or not.

Network Layer Model
The traditional Network stack model (OSI model) does not provide prioritization of traffic (they work on the Best-Effort model). So, in order to understand the implications of giving preferential treatment to some data, we need to look at the stack and see what changes will have to be made to incorporate this functionality in the system.

The OSI network layer model consists of seven layers each providing some functionalities and working together to fulffill the overall network goal.

• Physical Layer: Ensures that each bit reaches the next node correctly (e.g. using errorcontrol codes). This consitutes the hardware used for communication.
• DataLink Layer: This needs to take care of the sequencing of packets, issues like channel sharing in shared access environments (MAC) etc.
• Network Layer: Ensures the routing of packets and that they reach the desitnation.
• Transport Layer: This ensures that the packets reaches the correct process on the remote host.
• Session/Presentation Layers: Segmentation and Reassembly and providing the userinterface functions.
• Application Layer: This is the user layer.

Now, we are adding another functionality to the system prioritizing packets. Thus, the above layers will have to take up additional responsibilities so that we can provide the required features. Before deciding on how actually each layer will change, we need to define the framework in which QoS will be provided in the network, i.e. we need to define a QoS Model.

The model can be broadly of two types one in which we store the QoS parameters of each flow (connection) (Flow based approach e.g. IntServ Model in the Internet) and another in which we classify the data as a class based approach, i.e. the data flows are divided into a number of distinct classes with each class being provided a prespecified level of service termed as the Class of Service (CoS) e.g. DiffServ Model in the Internet.

Many authors note that the latter model is more applicable to MANets since a flow based approach requires a lot of data storage and processing which can be a drainage of resources in the already low resource mobile nodes. Some have also tried to bring about a mixture of both the approaches and proposed FQMM (Flexible QoS Model for Manets) [FQMM].

Thus, we assume three classes of service (Gold, Silver and Bronze). With such a framework, we need to see how will each of the layers in the stack get additional functionality. Looking at the stack top to bottom, we can have the following as one way of dealing with the service prioritization :

• Application Layer: Requests a particular CoS and adaptively changes its CoS depending on the network state (using feedback from the network) so that its packets are not rejected if the network fails to keep up with the desired CoS.
  
  
• Session/Presentation Layers: These can act as classifiers to distinguish between the different CoS and map data belonging to different classes to separate queues for the Transport Layer.
  
  
• Transport Layer: Services the higher CoS queue more often using some arbitration and maps the three classes of service to different Network Layer channels (different routing protocol for each CoS).
  
  
• Network Layer: Seeing each CoS data differently, it uses different routing mechanisms for each of them and sends the data into three different queues for the DataLink Layer.
  
  
• DataLink Layer: Uses different protocols again for different CoS so that faster, better and assured service can be delivered to e.g. the Gold CoS. It will also have to take care of the MAC issues to make sure that the CoS can be delivered.
  
  
• Physical Layer: This again may use better error correction schemes and may give more time for transmission to higher CoS. Also, it may adaptively try to change the modulation scheme etc. w.r.t the state of the channel and hence try to provide service even when the channel BER is high.

A point to be noted here is that the distinction between different CoS may not be implemented at each layer (e.g. the physical layer may not need it). We can have the following scenarios for each layer:

• The layer recognizes different CoS differently and provides them with different service. Also it has three queues at its input which it serves with some arbitration so that the higher CoS gets served faster.
• The layer recognizes different CoS (i.e. serves them differently), but has only one queue at its input.
• The layer does not distinguish between different QoS. This sort of a scheme may be used for the physical layer.

Now, which of the above three is the best technique for which layer, needs to be investigated.

QoS Analysis
In the previous section, we looked at each of the layers and their contribution towards ensuring QoS guarantees in the network. We can also look at the issue from the QoS provider point of view, i.e. seeing what all is required to ensure a particular CoS. Broadly speaking, we can divide the framework into the following :

• QoS Model
  This is the overall goal which the network wants to achieve. In our example above, the characterization of the incoming data traffic into Gold, Silver and Bronze classes forms the QoS Model.
  
  Current Work
  QoS Models have been defined for the internet (IntServ and DiffServ).
  • The IntServ Model is not direclty applicable to MANets due to the large amount of storage and processing needed in it. In this the nodes store the QoS characterizations of each flow.
  • The DiffServ Model is a good model which can be extended to MANets.
  • FQMM has been proposed as an intermediate between IntServ and DiffServ. In this the system is class based but the flow with the maximum QoS requirements is stored on a flow basis (i.e. the flow with the maximum QoS requirement is serviced on a flow basis but subsequent ones will have to be served on a class basis).
  • iMAQ framework is also one attempt towards a new look at the network stack and different layers providing different functionalities.
    
    
    
• QoS Resource Reservation
  Each flow on which we have provided some QoS guarantee will have to be allocated some resources which will be exclusively for its use. This will ensure that as soon as the packet of that particular flow comes, it will not have to wait for some path or resource to be freed and it will be transmitted to the next node `instantly'.
  
  Another issue that comes up here is that what resources to be reserved for a given set of QoS parameters and how will they be freed when the flow is terminated. Signalling that a particular set of resources have been allocated is also an issue to be dealt with. In our example since we are only supporting a fixed hierarchy of CoS, we can predetermine which resources to allocate for which service type.
  It is not very clear to me which layer will provide the functionality of resource reservation and signalling in the stack.
  
  Signalling that a particular resource has been allocated for a particular flow can be done in two ways :-
  • In-Band Signalling: In this, the signalling information is piggybacked on the data packet. i.e. the current data packet will carry information about the next packet.
  • Out-of-Band Signalling: In this, the signalling information is exchanged through a separate channel between the nodes. This consumes more bandwidth and leads to an increase in network traffic. The signalling packets in this compete with the data packets for bandwidth and hence is not suitable for resource limited MANets.
    
    Thus, In-Band Signalling seems promising for MANets.
    
    

  Current Work
  The following find mention in literature:

  • RSVP is used as the signalling protocol for IntServ QoS Model in the Internet. It is an Out-of-Band signalling protocol and hence is not suitable for MANets.
  • INSIGNIA has been developed exclusively for MANets but it works for a flowbased QoS model and so does not seem like an ideal solution to me.
    

• QoS Routing
  This needs to be ensured by the Network Layer. The idea is to find a route to the destination which satisfies th QoS requirements. Such a routing is sometimes termed as `QoS Aware' routing. This forms a very important part of the overall picture since nodes are mobile and connections will break and will be made dynamically and hence, the routing protocol needs to take care of such situations.
  
  Current Work
  Some work has come up in this. At least two routing mechanisms have been proposed :
  • CEDAR
  • Ticket based Routing
    
    
    
• QoS Medium Access Control (MAC)
  Some Medium Access guarantee should be provided by the DataLink Layer for supporting the given QoS requirements. This plays a very important role in fulfilling the desired objectives since the transmitting node should get the required transmission time so that it can send the data to the next node. Collision Avoidance, Hidden Terminal and exposed terminal problems need
  to be solved.
  
  Current Work
  The following protocols find mention in literature :-
  • MACA/PR uses a RTSCTS dialog (loosely like serial RS232)
  • Black Burst Contention Scheme has been proposed. But it seems to be wasting power.
    

  Here, I think we should look at the 802.11 and Bluetooth MAC protocols and see if they are applicable to MANets or not.

REFERENCES

1. S. Chakarabarty and A. Mishra, QoS Issues in AdHoc Wireless Networks, IEEE Communications Magazine, February 2001.
2. Kui Wu and Janelle Harms, QoS Support in Mobile Ad Hoc Networks, http://cs.ualberta.ca/~wkui/research/QoSReview.ps
3. P. Mohapatra, J. Li and C. Gui, QoS in Mobile AdHoc Networks, http://www.cs.ucdavis.edu/~prasant/pubs/tr/survey.pdf
4. Zeinalipour-Yazti Demetrios, A glance at Quality of Service in Mobile AdHoc Networks, http://www.cs.ucr.edu/~csyiazti/cs260.html
5. [IntServ/RSVP] R. Braden, D.Clark, and S. Shenker, Integrated Services in the Internet Architecture an Overview, IETF RFC1663, June 1994.
6. [DiffServ] S. Blake, "An Architecture for Differentated Services, IETF RFC2475, December 1998.
7. [FQMM] H. Xiao, W.K.G. Seah, A. Lo and K.C. Chua, "A Flexible Quality of Service Model for Mobile AdHoc Networks, IEEE VTC2000 spring, Tokyo, Japan, May 2000.
8. [INSIGNIA] S.B. Lee and A.T. Campbell, INSIGNIA: Inband Signalling Support for QoS in Mobile AdHoc Networks, Proc. of 5th International Workshop on Mobile Multimedia Communications (MoMuC, 98), Berlin, Germany, October 1998.
9. [CEDAR] P. Sinha, R. Sivakumar, and V. Bharagavan, CEDAR: a Core Extraction Distributed Ad hoc Routing algorithm, IEEE Infocom '99, New York, NY. March 1999.
10. [Ticket-based] S. Chen and K. Nahrstedt, Disributed Quality of Service Routing in Ad-Hoc Networks, IEEE Journal on Special Areas in Communication,Vol 17, No. 8, August 1999.
11. [MACA/PR] C. R. Lin and M. Gerla, "MACA/PR: An Asynchronous Multimedia Multihop Wireless Network, Proceedings of IEEE Infocom'97,1997.
12. [BlackBurst] Special Issue on Wireless AdHoc Networks, IEEE Journal on Selected Areas in Communications, Aug. 1999.