Simulation & Performance Evaluation of QoS Routing Protocol for Adhoc Networks Using Directional Communication ()
1. Introduction
An ad-hoc network is a dynamic network formed on demand by a group of nodes without any pre-existing network infrastructure. Wireless ad-hoc network may be classified in two types, Mobile Ad-hoc Network (MANET) and Stationary Ad-hoc Network (SANET). Selfconfigurability and easy deployment feature of the Mobile Ad-hoc network (MANET) resulted in numerous applications in modern era. Community network, military and emergency rescue are some application of adhoc network where infrastructure is unavailable or difficult to install. Directional antenna offers the great benefits for wireless ad-hoc networks, with directional transmission and reception. With increasing application of ad-hoc wireless network, the need for supporting quality of service (QoS) is becoming essential. However, Distributed Coordination Function (DCF) [1] MAC (Medium Access Control) of IEEE 802.11, which is the most widely used MAC protocol in MANETs, does not support the QoS in MANETs due to its inherent problems [2,3].
Our main concern is to propose a QoS routing protocol for wireless ad-hoc network using directional antenna and directional MAC based on the priority assigned to traffic. Any source node can assign high priority or normal priority to flow generated by it. If a high priority flow is running in the network, nodes and their respective beam used for this high priority communication are set as reserved node and communication zone formed is called as reserved zone. Normal priority flows will try to avoid the high priority reserved zone and that will reduce the interference of normal priority flow with high priority flow. It is not necessary that normal priority flow always found the disjoint path. As number of high priority flow increases, it is difficult for normal priority flow to find the disjoint path. It may happen that normal priority flow always search for disjoint path but never reach the destination.
A concept of call blocking is being used to improve the performance of high priority flow. In call blocking normal priority, flows are forced to block their communication if no disjoint paths are available. But, in the case of without call blocking, normal priority flows are allowed to use the coupled paths with high priority flows that reduce the performance of high priority flow. This QoS routing scheme improves the performance of high priority traffic in term of timely and reliable delivery. Major application of this scheme will be area of medical emergency, roadblock or traffic control and battle field where emergency massage is required to propagate with high priority.
The remainder of this paper is organized as follows. Section 2 describes the related work already done. Section 3, presents the basic definitions and some basic concepts of antenna, network model used, coupling factor, zone disjointness, priority assignment and network topology information update. Section 4 describes zone disjoint routing and QoS routing. Section 5 discusses the performance evaluation, which includes the simulation setup and results; finally, Section 6 concludes the paper.
2. Related Works
One major challenge of routing protocols is data delivery to destination in wireless ad-hoc network. They must define efficient and balanced way of data forwarding (routing). Nemours routing protocol have been proposed for ad-hoc network using omni-directional antenna. These routing protocols are categorized by network topology change, quality of service, and bandwidth constraints etc. To improve the performance of ad-hoc network directional routing protocols with directional antenna with multiple beams are being used [4-6]. For efficient utilization of directional antenna different directional MAC protocols has been proposed [7-10]. To support quality of service in wireless network different QoS based schemes have been proposed [11-15]. In paper [14] authors addressed the problem of supporting real-time communications in a multi-hop mobile network using QoS routing, and proposed a protocol for QoS routing. S. Chen and K. Nahrstedt proposed a ticket-based probing algorithm [11] for QoS routing in MANETs.
QoS routing protocols search for routes with sufficient resources for QoS requirements. The QoS routing protocols should work together with resource management to establish paths through the network that meet end-to-end QoS requirements, such as delay jitter bound, bandwidth demand, or multiple constraints. Siuli Roy et al. [16] proposed an adaptive routing protocol with maximally zone disjoint shortest path and they used this scheme to balance the traffic load using multipath routing. In this, node should detect the signal strength and angle of arrival of each signal it hear and maintains a table that will be used to find the location of neighbors. They used the directional antenna at physical layer and 802.11 MAC at MAC layer, which did not fully exploit the features of directional antenna. Further, they used this scheme for QoS support to priority-based traffic [12].
3. Basic Concepts
3.1. Antenna and Network Model Used
In switched beam directional antenna model, each node have M highly directional, fixed predefined antenna beam elements which are deployed into non overlapping fixed sectors, each spanning an angle of 360/M degree. Each node can operate in two modes: Omni-directional and directional mode. When node operates in omni-directional mode, it is capable of transmitting and receiving signals from all direction. In directional mode, node can point its beam in specific direction and transmit directionally but it receives omni-directionally. It is assumed that, antenna gain in both mode of operation, omni-directional (Gomni) and directional (Gdir) are equal. Switched beam antenna is comprised of multiple fixed beams that are formed by shifting the phase of each antenna element of an antenna array by a predetermined amount, or simply by switching between several fixed directional antennas. Switched beam directional antenna with four beams (beam number 0 to 3) is used for simulation as shown in Figure 1.
An ad-hoc network is modeled as a graph G = (M), where M is finite set of nodes. Node Ni has a set of neighbors NBi = {Nj Є M} and Nj is located in the transmission zone formed by any beam of node Ni. Transmission beam (TB) of node Ni having four transmission beams (0, 1, 2 and 3) is represented as TBi,z where z = 0, 1, 2 and 3. So node Ni has the transmission beams TBi,0, TBi,1, TBi,2, TBi,3. Transmission zone formed by beam of node Ni is represented as TZi,z where z = 0, 1, 2 and 3. Transmission zone formed by node Ni are TZi,0, TZi,1, TZi,2, TZi,3. In single channel systems, nodes transmit and receive on the same shared channel. Neighboring transmitters contend for channel access by means of a media access control protocol. When node Ni transmit to node Nj by using the beam TBi,z then other nodes located in the transmission zone TZi,z should sit idle to avoid the collision. Nodes located in other transmission zone of node Ni can participate in the other transmission. Communication ID Cn is a unique identification (ID) number assign to each communication initiated for specific source destination pair.
3.2. Route Coupling and Disjointness
Ad hoc network can be implemented by single channel or multi channel. In single channel systems, nodes transmit and receive on the same shared channel. Single channel system has significant impact on the performance due to route coupling. Two routes are said to be coupled if they have common nodes or links. Two nodes are said to be coupled, if they are physically close enough to interfere the transmission of each other. Two routes are physically close to interfere with each other during transmission is called as route coupling. Coupling factor 
of node Ni in a path P for communication ID Cn is define as the sum of number of communication ID handled by each
Figure 1. Simultaneous transmission through coupled routes using directional antenna.
active neighbor of node Ni in the transmission zone TZi,z excluding the current communication ID Cn, TZi,z is the transmission zone formed by the node Ni toward neighbor Nj in the path P. Coupling factor 
of node Ni is as follow:
(1)
where C is number of all communications through active neighbors of node Ni (Act NBi) using transmission zone TZi,z including current communication Cn and Act NBi is active neighbor nodes of Ni participate in any communication.
Coupling factor of path P for communication ID Cn[ηCn(P)] is define as the coupling factor of all nodes in the path P. Path coupling factor [ηCn(P)] is given as:
(2)
where Ni is number of node starting from source to destination in path P used for communication ID Cn. From the Figure 1, node A use its transmission zone TZA,0, TZA,1, TZA,2, TZA,3 formed by the beam 0, 1, 2 and 3 to communicate node (C, N), F, E and B respectively. So node A has a set of neighbor nodes NBA = {(C, N), F, E, B}.
Two flows having the communication IDs C1 and C2 start from nodes E to C and L to K. Routing path used for communication are E-A-C and L-B-G-K. Using omnidirectional antenna these two routes are coupled with each other. Transmission zone of node L using the omnidirectional antenna is around the node L in coverage range of R. Node E is in the transmission zone of node L and vice-versa. Coupling factor of node L can be calculated by using question (1) as follow: Act NBL = 2, two active neighbors E and B participate in communications C1 and C2 respectively so coupling factor of node L will be 1, 
, because node B participate in the communication C2 itself. Similarly active neighbors of node B (Act NBB) are L, A and G. Coupling factor of node B will be 1, 
because L and G participate in flow (communication) C2. Coupling factor of node G 
will be one and for node K will be zero. Coupling factor of path P used by the flow C2 [ηCn(P)] will be coupling factor of all nodes (L, B, G, K) in path P that will be 1 + 1 + 1 = 3. It represents that two paths used by the flows C1 and C2 are coupled (joint) to each other by factor of three using the omni-directional antenna.
When directional transmission is used at each node and only two flows C1 and C2 are initiated, paths (P1 and P2 respectively) used by these flows are fully disjoint. Node B is located in the transmission zone TZL,0 formed by the beam TBL,0 of node L. There is only one active neighbor node B in the transmission zone TZL,0. Node B participates in the flow C2 only, no other flows go through this node. So coupling factor of node L 
will be zero. All other nodes (B, G and K) in path P2 have the coupling factor zero because these nodes participate in only flow C2. So coupling factor of path P2 used by flow C2, [ηC2(P2)] is zero. Similarly coupling factor of path P1 used by flow C1 [ηC1(P1)] will be zero. These two active paths are fully disjoint by using directional transmission. Using the directional transmission routes E-A-C and L-B-G-K are fully disjoint so both communications can run at simultaneously without affecting the performance of each other.
Third flow with communication ID C3 initiated from node M to J using the path P3 (M,F,A,N,G,K,J). Path P3 is coupled with both active path P1 and P2. Path P3 is coupled with P1 and P2 individually by factor of two. Total coupling factor of P3 with all other active path is four.
3.3. Priority Assignment
Any source may assign priority to the flow according to the type of traffic or flow initiated, that might be high and normal priority flow. Transmission zone formed by the high priority flow is called as high priority communication zone. If a high priority communication is going on between node A to node B using the beam 1 and 3 of node A and B respectively. Then transmission zone formed by these beams (beam 1 of node A and beam 3 of node B) is called as high priority reserved zone. All nodes belongs to any high priority communication are reserved as high priority reserved node. Node A and B are reserved as high priority reserved nodes so that other flows avoid this zone to reduce the interference. Each node maintains the reserved node list that have the information of all reserved nodes of entire network. This reserved node list should be updated regularly and forwarded to other neighbors. If reserved node does not receive the high priority packet for certain duration of time, it will becomes unreserved node and modify its table.
3.4. Network Topology Update
At the MAC layer, circular MAC is being used. In this scheme RTS (request to send) is transmitted directionally in circular way until it scan all the area around the transmitter. If the node is the destination of RTS it will send the CTS (clear to send) directionally toward the source of RTS node. Nodes receive and transmit the CTS, DATA and ACK (acknowledgement) Omni-directionally and directionally respectively. As shown in Figure 1 node A want to communicate with node B, it start transmitting RTS using beam 0. After short duration of time, same RTS with next beam (beam 1). This process is continuous until node A covers all area around it. Node B sends the CTS directionally toward the node A using beam 1. Nodes A use beam 3 to transmit to B that use beam 1 to receive. Similarly, node B use beam 1 to transmit and node A use beam 3 to receive.
3.4.1. Neighbor Node Beam Table (NNBT)
Each node maintains a table, called node beam table (NNBT), with one entry of each node it has heard. Initially node beam table is empty and it is updated with information received by neighbor node in form beacon signal. Due to mobility of node, table may be updated regularly. In every record, the nodes maintain the following information: Me (itself), Neighbor (the node from which it receives a packet), My beam (the beam by which the transmitter receives the packet), Neighbor’s beam (the beam by which receiver sent the packet) [10]. Table 1 illustrates the NNBT maintain by node A. One entry for each node, first entry show that A use beam 3 to connect node B and B use beam 1 to connect node A.
3.4.2. Node Activity List (NAL)
On the basic of activity information of all nodes in the network, each node prepares its node activity list. This contents node ID, status (0 for inactive, 1 for active with normal priority flow, and 2 for high priority flow), communication IDs (flow ID) for which that node being used as shown in Table 2. In second column, communication Id C1 and C2 indicates that flow C1 and C2 use node A in it routes. In third column all communication Id field are 0, it show that node B is not involve in any flow (communication). Second flow C2 is normal priority flow that uses the route E, A and F so status of node E and F are set as 1. Initially, when networks start working each node have activity information of neighbors only. Each node periodically broadcast the node activity list to its neighbors. After receiving the NAL from its neighbors each node update its NAL and broadcast to their neighbors after regular interval. Using this process each node capture the activity status of all node in the network. Entry of each neighbors in NAL are time stamped. If any node receives the update message from different node related
Table 1. Neighbor node beam table at node A.
Table 2. Node activity list at node A.
to same node then recent message is accepted and older one is rejected, so each node know the latest activity status of all nodes.
3.4.3. Global Node Beam Table (GNBT)
In Each node maintains a global node beam table (GNBT) to capture the networks topology information. Each node broadcast its NNBT periodically and it serves as beacon. GBNT updated by the NNBT of that node. During initial phase of network topology generation, each node has the information of its neighbors only and no information about the network connectivity. Each node broadcast its GNBT to its neighbors. Therefore, each node update its GNBT based on the update message received from the neighbor’s GNBT. This update message is being slowly propagated from one node to other node. Now, node has the information of their neighbors and all other nodes in the network. If two GNBT update message have a set of data for same node, recent update message that have most recent information about the node is used, and old one is discarded. In GNBT first column is node ID and second column is neighbor nodes and beam number use to communicate these neighbors. First row of the Table 3 and Figure 1, illustrate that node A use beam number 3 to communicate node B, similarly beam number 0, 1 and 2 are use to communicate node C, F and E respectively. Structure of NNBT, NAL and GNBT are very simple and smaller in size compare to routing protocol presented by authors in [12].
4. QoS Routing
4.1. Zone-Disjoint Routing
In this sub-section, a zone-disjoint routing protocol is discussed using directional antenna. Zone-disjoint routing protocol will reduce the coupling factor, so it reduces the interference of active routes in the network. It allows to select the routes for each communication that are maximal disjoint to other active routes. Each node has the latest status of all nodes and communications activity at any instant of time by the node activity list and global node beam table. Based on this information, routing path of each flow are selected.
As illustrated in Figure 2, first flow with ID C1,
Table 3. Global node beam table at node A.
Figure 2. Fixed topology of 10 nodes using directional antenna.
started from A to E. It will search for the shortest and disjoint path. Shortest path P1, which will be use for communication is A-B-E. This path is fully disjoint because this is only flow present in the network. Node activity list is updated and communicated to neighbor nodes and this update message is passed to other nodes in entire network. Second flow with ID C2 started after some time from node F to node D. Multiple paths P2{F-A-B-C-D}, P3{F-A-B-E-D} and P4{F-H-I-J-D} are available. Maximal disjoint shortest path will be selected. Coupling factor of path P2 with path P1 will be sum of coupling factor of all node (F, A, B, C, D) in path P2. Coupling factor of node B, C, D and E will be zero. Coupling factor of node F participate in flow C2 
will be one, because active neighbor of node F is A only which participate in both flow C1 and C2. Coupling factor of node A 
will be one. Coupling factor of path P2 (hop count is 4) used by flow C2 [ηC2(P2)] will be two. Similarly coupling factor of path P3 (hop count is 4) [ηC2(P3)] will be three. Coupling factor of path P4 (hop count 4) is zero. Routing path Pj for flow Cn will be selected, having the lower value of 
where H is hop count of path Pj that is limited to maximum value of 18. Path P4 (F-H-I-J-D) will be selected because it has zero coupling factors, so it is fully disjoint with other active paths. Updated node activity list at node D is forwarded to other nodes in entire network. Other node will modify their activity table and global node beam table (GNBT).
Third flow initiated after some time form node D to node B. Paths available for this flow are P1 = {D-C-B}, P2 = {D-E-B} and P3 = {D-J-I-H-F-A-B} having the hop count 3, 3 and 6 respectively. Path P3 having lower (coupling factor * hop count) is selected for communication.
4.2. Zone Disjoint QoS Routing
Source assigns the high or normal priority to flow depending upon the type of traffic. When any high priority communication is running in network, then normal priority flow will try to avoid the path used by high priority flow and it will search for disjoint path but it is limited to maximum hop count. Otherwise normal priority packets move around the network in search of disjoint path but may not reach the destination. To avoid this maximum number of hop count is limited to 18 [12].
When any high priority communication is started from source to destination, it will try to search shortest path, all the nodes in this path set their activity as high priority node, and they are reserved for this specific high priority communication. Status information of nodes is updated in NAL and reserved node activity information is periodically transmitted to all other nodes in the net-work. All other nodes update their information of reserved nodes in the network. If any node reserved for high priority communication does not receive the high priority packet for certain duration of time, it will change its status form high priority to normal priority and update their node activity list. This update information is transmitted to other nodes also.
4.2.1. Routing without Call Blocking
Initially a high priority communication is initiated form A to E. As given network topology in Figure 2, if no other communication is running it will search for shortest path only based on global node beam list and node activity table that is {A-B-E}. All nodes through this path set as reserved node and set status field as 2 in node activity table. Node activity table of B is updated and this update massage is transmitted to entire network. The entire nodes in network update their node activity table based on updated massage received from neighbors. After some time a normal priority flow is started from C to F. Multiple routing paths are found using the global node beam list. Paths available from C to F are P1{C-B-A-F} and P2{C-D-J-I-H-F}. It will calculate the coupling factor of each nodes and path involved in communication using Equations (1) and (2). Path P2 is disjoint path while P1 is joint (coupled) with high priority flow active path. Disjoint path P2 is selected for normal priority communication.
Suppose node H is not present in the network and normal priority flow from node C to F is initiated. It will search for disjoint path but no disjoint paths are available. Shortest path {C-B-A-F} is available that is coupled with path used by high priority flow. If call blocking is not implemented normal priority flow is forced to use the coupled path and that will degrade the performance of high priority flow. To guarantee the minimum bandwidth requirement of high priority flows, rate of normal priority flows are regulated.
4.2.2. Routing with Call Blocking
If call blocking is implemented then normal priority flow will be blocked because normal priority flow are not allow to use the node that are reserved for high priority flow in their routing path. If normal priority flow is blocked only high priority flow will be in network that improves the performance of high priority flow. All nodes regularly check the node activity table for reserved node status. If any reserved node does not receive the high priority flow packets it reset as normal flow, and reset the status field as one. This update massage is transmitted to other node and all nodes change the status of that node. Flow chart for QoS routing without call blocking and with call blocking is given in Figure 3.
5. Performance Evaluation
5.1. Simulation Setup
Simulation is done on Qualnet [17] that is written using PARSEC [18], a C language base discrete event simulator. Traffic model used in our simulation is CBR with packet size of 512 bytes and packet transmission interval 2 ms to 100 ms. Directional and omni-directional transmission range is 250 m. Data transmission rate is 2 Mbps. The simulations have been done for different random seed and the results are statistically averaged out for 10 iterations, each running for 300-simulation seconds. There was no network partition throughout the simulation. The simulation has been done in various network scenarios to assess the performance of protocols.
5.2. Performance of Random Topology with 10 Nodes
In this scenario stationary ad-hoc network with random topology and 10 nodes has been taken in area of 1000 × 1000 m. For first case without priority (normal priority) simulations has been done considering different conditions.
• Only single flow (flow 1) from node A to node E that gives the high throughput and normal delay because no coupling path with other active flow;
• Other three flows from different source destination combination has been taken flow 2 (C-F), flow 3 (B-I) and flow 4 (D-A). These simulations have been repeated for different combination of source and destination for all flow with different seed value. As illustrated in Figure 4 throughput of flow1 is high when only flow 1 is present in the network. Throughput re-
Figure 3. Flow chart of QoS routing protocol for without and with call blocking.
duced when all four flow (flow 1, flow 2, flow 3 and flow 4) are active because routing path used by these paths are coupled with other active path;
• In last case one flow out of four is assigned as high priority and other three are assigned as normal priority. This simulation is done assuming one flow of different source destination combination as high priority and other three flows as normal priority and they are coupled with high priority flow path. In this case flow having high priority shows the considerable improvement in throughput with compare to the flows without priority.
Figure 5 shows the performance of flow 2-flow 4 without assigning flow1 as high priority throughput of normal