Performance Analysis of Spatial Reused Bandwidth Reservation in Ad Hoc Networks

Published Online November 2010 in MECS

A mobile ad hoc network consists of wireless nodes that communicate with each other in the absence of a fixed wireless network infrastructure. Nodes cooperate to forward data packets with each other, thus a node can communicate with another node by multi-hop.

In the mobile ad hoc network, node mobility causes unpredictable topology change, the research and design of quality of service (QoS) guarantee is more complicated than traditional networks. The ability to provide QoS guarantee is dependent on how well the channel resources are managed by the protocol at the medium access control (MAC) layer [1].

MAC protocols can be classified into two categories: contention-based MAC protocols and scheduled-based MAC protocols. The contention-based nature makes contention-based MAC protocols difficult to allocate and reserve bandwidth, which is desired by real-time multimedia application, such as audio/video conferencing.

Manuscript received March 16, 2010;

Because each node that has been assigned a set of time slots can transmit data packets, schedule-based MAC protocols are potentially better suited to support QoS guarantee by reserving bandwidth and following the rule of the transmission schedule.

Scheduled-based MAC protocols can be classified into two categories: topology-dependent scheduling and topology-transparent scheduling. The topology-transparent scheduling does not need any topology information to perform transmission scheduling, and can guarantee that every node has at least one collision-free transmission slot in each schdule cycle (i.e., single-hop QoS support) provided some constrains are satisfied [1].

In the topology-dependent scheduling, each node finds conflict-free time slots by using network topology information. The topology-dependent scheduling concentrats on finding conflict-free schduling which maximizes the system performance by using network topology information [2].

Recently, the Time Division Multiple Access (TDMA) scheme is the most prevalent approach in topologydependent scheduling MAC protocol. In order to provide the guaranteed bandwidth along a path, the bandwidth must be reserved along the entire path. In wireless networks, nodes use their reserved slots to transmit data without collisions. In the assumed Time Division Multiple Access (TDMA) model [2], the use of a time slot for a link depends on the status of its 2-hop reighboring links. TDMA-based QoS routing protocols take the slot assignment and interference into consideration [3, 4].

A stronger channel model Code Division Multiple Access (CDMA)-over-TDMA was adopted to relieve the link interference [5]. The use of a time slot on a link only depends on the status of its 1-hop neighboring links. When the bandwidth requirement is high and the network resource is rare, multi-path QoS routing protocols are developed to provide QoS support in CDMA-over-TDMA wireless ad hoc networks [6, 7, 8, 9].

A genetic algorithm was used to maximize the available path bandwidth along a path [10]. Based on this genetic algorithm, an improved parallel genetic algorithm for bandwidth calculation is proposed in [11]. Espes and Mammeri have presented a TDMA-based routing protocol to meet delay and bandwidth requirements while optimizing network throughput [12].

YuhShyan Chen has presented a hexagonal-tree TDMA-based QoS multicasting protocol [13]. In [14], Kapoor proposes a greedy framework for distributed scheduling, which provides an efficient and integrated solution to QoS aware routing and call admission control in distributed WiMAX mesh networks. These TDMA-based bandwidth reservation protocols use the omnidirectional antennas.

In [15], Jawhar and Wu have proposed a race-free routing protocol for quality of service support in TDMA-based wireless networks, which allows a source node to find and reserve a path with a certain required bandwidth (expressed in terms of the number of data slots) to a destination node. This protocol is extended to do path reservation in TDMA-based wireless networks, where the nodes are equipped with directional antennas [16].

In this paper, we propose a scheme for spatial reused bandwidth reservation for multi-path routing protocol in TDMA-based ad hoc networks by using directional MultiBeam Adaptive Array (MBAA)-antennas. It is different from the above protocols in that it is not only on-demand, based on the Dynamic Source Routing (DSR) protocol, but also based on the multi-path search strategy.

Our protocol tries to discover multiple node-disjoint paths between the given source node and the destination node, and the total bandwidth of these paths can satisfy the bandwidth requirement of the application. This is in contrast to above protocols which find a bandwidth siatisfied path between the source and the destination.

Our work is different from those multi-path QoS routing protocols in [17, 18]. The reason is that the nodes in TDMA-based wireless networks are equipped with directional antennas in our paper. The bandwidth requirement of an application is specified in terms of number of data slots required for transmission and reception at a node. Each node uses a mechanism for determining the slots that it can use for transmission and reception of data. The source node tries to identify multiple node-disjoint paths from itself to the destination. The destination is responsible for bandwidth reservation along the paths identified so that the total bandwidth of these paths can meet the bandwidth requirement.

The rest of this paper is organized as follows: Section П describes the related works. In Section Ш , a spatial reused bandwidth reservation for multi-path QoS routing protocol by using directional antennas is presented. The simulation results are provided in Section IV . Section V concludes this paper.

• II.    R ELATED W ORKS

In wireless networks, nodes transmit data packages by using an omnidirectional antenna that radiates its power equally in all directions. This is a transmission mode of omnidirectional antennas. The transmission mode of directional antennas allows a node transmit data packages in a particular direction. At the same time, a receiving node can focus its antenna in a particular direction.

Figure 1. Transmission mode of omnidirectional antennas

(a) Transmission mode

(b) Reception mode

(c) Communication mode

Figure 2. Transmission mode of directional antennas

Figure.1 shows the transmission mode of omnidirectional antennas, a sending node transmits data packages at all the directionans.

Figure.2 shows the transmission mode of directional antennas. Fig. 2 (a) shows a sending node equipped with a MBAA antenna array with four beams. This node transmits data packages at these four directions. Fig. 2 (b) shows a receiving node equipped with a MBAA antenna array with four beams. This node receives data packages at these four directions. Fig.2 (c) shows the communication mode from tranmitter A to receiver B . The node B is at the sending direction of node A , and node A is at the receiving direction of node B .

Directional antenna technology provides the following advantages [16]: (1) a smaller amount of power can be used; (2) other nodes can use the surrounding area in the other directions to transmit, which increases the spatial reuse; (3) route has shorter hops and smaller end-to-end delay. In this paper, a MultiBeam Adaptive Array (MBAA) system in [19] is used and is capable of forming multiple beams for simultaneous transmissions or receptions in different directions.

In wireless ad hoc networks, providing quality of service support is a challenging task. The reason comes from the dynamic topology of network, which may not allow consistent resource reservation. A single path may not be able to provide enough bandwidth resources so as to meet higher quality of service requirement when the network load is heavy. Therefore, it is necessary to consider satisfying higher quality of service requirement through resources that may be reserved along multiple paths from a source to a destination.

Figure 3. Hidden terminal problem

Figure 4. Exposed terminal problem

A

B

{ 2 ,3,4}

C

D

E

F

{ 4 , 5 }

{1, 2 , 3 }

S

{2, 3 ,4, 5 }

LB(S, A)=|{1,2}|=2

LB(A, B)=|{1,2}|=2 LB(B, D)=|{2,3}|=2 { 4 , 5 }

PB(SABD)=1

PB(SCD)=1

{ 3 , 4 }

Figure 5.The slot allocation using omnidirectional antennas

The TDMA channel model is assumed to be time-slotted. TDMA frame consists of a control subframe and a data subframe [3]. The control subframe consists of N D fixed-length data slots. The data subframe contains N C fixed-length control slots.

In wireless networks, the hidden terminal problem and exposed terminal problem may also occur. In Figure. 3, node A and node B are 1-hop neighbors, node B and node C are 1-hop neighbors, and node A and node C are not 1-hop neighbors. The transmissions of node A and node C will collide at node B . This is known as hidden terminal problem.

In Figure 4, node S 1 and node R 1 are 1-hop neighbors, and node S 2 and node R 2 are 1-hop neighbors. At the same time, node S 1 and node S 2 are 1-hop neighbors. If node S 1 is transmitting data packets to node R 1, then node S 2 can not transmit data packets to node R 2. This is known as exposed terminal problem.

In fact, the transmissions of node S 1 and node S 2 will not collide with each other in wireless networks. Therefore, a major challenge in wireless network is that how to remove the hidden terminal problem and exploit terminal problem.

In TDMA-based wireless network, the available bandwidth along a link is an intersection of the sets of data slots available at two nodes of the link [2]. In Figure 3, there is a link between node A and node B . Let the set of the available free slots at node A be {1, 3, 4}, and the set of the available free slots at node B be {1, 4}. Link Bandwidth ( LB ) is defined as the element number in set of slots that are marked as “free” in end nodes of a link. LB ( AB ) = | Free_Slots( A ) I Free_Slots( B ) | = |{1, 3, 4} I {1, 4}|= |{1, 4}| = 2. Therefore, the avaliable bandwidth of the link ( A , B ) is two slots.

Now consider a scenario in TDMA-based ad hoc network. There are three node-disjoint paths in Figure 5, namely, {S, A, B, D}, {S, C, D}, and {S, E, F, D}. Let bandwidth requirement of the application is two slots.

It seems that the available bandwidth of the path {S, A, B, D} can satisfy the bandwidth requirement of the application as the minimum number of available slots at links is two slots. In fact, this path does not satisfy the bandwidth requirement of the application. The reason is that nodes allowed transmitting data packages or receiving data packages in the available slots that should not be used by any of their 2-hop neighbors [3].

Therefore, the allocated slot on link (S, A) is one slot. The slot {2} and slot {3} are allocated on the link (A, B) and link (B, D). The path bandwidth ( PB ) is defined as the minimum link bandwidth along the path. Therefore, the path bandwidth of the path {S, A, B, D} is one slot.

In the second path {S, C, D} in Figure 5, the slot {2} and slot {4} are allocated on the link (S, C) and link (C, D). The path bandwidth of the path {S, C, D} is one slot. The total bandwidth of these two node-disjoint paths {S, A, B, D} and {S, C, D} is two slots, which can satisfy the bandwidth requirement of the application. From the above analysis, we can see that multiple node-disjoint paths can satisfy higher bandwidth requirement of the applicaion when the network load is heavy.

• III.    S PATIAL R EUSED B ANDWIDTH R ESERVATION

• A.    Definition and Suppossion

In this paper, we represent a static multi-hop wireless network with an undirected network graph G ( V , L ). Where V represents the set of nodes and L represents the set of links between the nodes. In wireless networks, we suppose that the interference range ( R I ) between two nodes is the twice of the transmission range ( R T ) of node.

• i .e., R I =2 x R T .

Suppose there are a source node S and a destination node D . Our purpose is to find paths form the source node S to the destiantion node D , and these paths can satisfy the quality of service requirement of the application.

In order to support the spatial reused bandwidth reservation for multi-path QoS routing protocol in TDMA-based ad hoc networks by using directional antennas, the following definition are given.

Definition 1:

The bandwidth of a link in the path is defined as the common free slots at two end nodes.

bandwidth (link (AB)) = free slots(A) I free slot(B) (1)

Definition 2:

The bandwidth of the path is defined as the minimum bandwidth of links in the path.

bandwidth (Path) = Min{link bandwidth i }        (2)

Definition 3:

If the path is interference-free scheduled, then any three consecutive links on a path are not assigned same time slots.

For any slot t , any interference-free link scheduling must satisfy the following condition. l 1 , l 2 and l 3 are three consecutive links in a path. T ( l i , t ) denotes whether the link l i use slot t to transmit data packages.

T (l i , t) + T (l 2 , t) + T (l з , t) <  1                 (3)

Definition 4:

If a uni-path can not meet the bandwidth requirement B , multiple node-disjoint paths will be used to transmit data packages. The total bandwidth of these node-disjoint paths can satisfy the bandwidth requirment of an application.

m

^ bandwidth (Path) ^ B (4)

i = 1

• B.    Data Structure

In our proposed the spatial reused bandwidth reservation for multi-path QoS routing protocol in TDMA-based ad hoc network, we suppose that each node x maintains the following three tables as local information: sending table (ST), receiving table (RT) and hop-count matrix (H).

The sending table of node x (ie., ST x [ i , j ]) contains the slot status for the 1-hop or 2-hop neighbor node i of node x for sending data packages. If slot j of node i has been reserved for sending data packages, then ST x [ i , j ] = 1; If slot j has been allocated for sending data packages, then ST x [ i , j ] = 0; Otherwise, slot j of node i is free and set the value of ST x [ i , j ] as -1.

The receiving table of node x (ie., RT x [ i , j ]) contains the slot status for the 1-hop or 2-hop neighbor node i of node x for receiving data packages. If slot j of node i has been reserved for receiving data packages, then RT x [ i , j ] = 1; If slot j has been allocated for receiving data packages, then RT x [ i , j ] = 0; Otherwise, slot j of node i is free and set the value of RT x [ i , j ] as -1.

The hop-count matrix H x [ i , j ] contains the neighborhood information about the 1-hop and 2-hop neighbor node i of node x . If node i and node j are 1-hop neighbor, then H x [ i , j ] = 1; Otherwise, H x [ i , j ] = 0 means that node j is not a neighbor of node i .

The above three tables also contain an angular groups field. The entry A[ a ] i^j denotes the set of angular groups to which the a th sending/receiving antenna is pointed. A[ a ] i^j =null indicates that the a th antenna for node i is not used during slot j .

• C.    Spatial Reused Bandwidth Reservation for Multipath QoS Routing

When a source node S wants to send data packages to a node D with a bandwidth requirement of B slots, it broadcasts a QoS Route Request (QREQ) package to all neighbors. This QREQ ( S , D , id , b , x , PATH , NH ) package contains the following fields:

• (1)    S is a source node;

• (2)    D is a destination node;

• (3)    id is identity of request;

• (4)    b is the bandwidth requirement of the application;

• (5)    x is a node currently relaying the QREQ package;

• (6)    PATH is path together with the available slots that has been discovered;

• (7)    NH is a list of next-hop nodes of node x , together with the format (( h 1 , l 1 ), ( h 2 , l 2 )… ( h n , l n )). h i has potential to serve as the next hop of node x , along with a list of slot l i . Node x may transmit data packages to neighbor node h i by using slots l ^’i .

When an intermediate node y receives a QREQ package from 1-hop neighbor node x , it will perform the following steps.

Firstly, node y will decide whether this QREQ package has been received before according to S and id . If yes, it will drop this QREQ package to avoid loop path. If node y has been in PATH , it will drop the RREQ package. If node y is not a node in NH , it drops the RREQ; Otherwise, suppose that the two-tuples ( h i , l i ) be belong to NH and the node y is the node h i . Then it adds two-tuples ( x , l i ) to PATH . At last, it updates x with h m +1 .

Before forwarding the QREQ package, node y creates temporary sending table (STtemp) and temporary receiving table (RTtemp). Then copies all entries in STy into STtemp, and copies all entries in RTy into RTtemp. Assign STtemp[hj, t] = STtemp[hj+1, t] =0 for each slot t in the list li (i=m, m+1). In order to avoid the hidden terminal problem, the same slot can’t be allocated to three consecutive links (i.e., lm, lm+1, l temp). Let NHtemp=null at first.

For every 1-hop neighbor node z of node y , do L = select_slot ( y , z , b , ST temp , RT temp ). The procedure select_slot ( y , z , b , ST temp , RT temp ) denotes find b free slots from link ( y , z ) according to the ST temp and RT temp . If L is not null, then NH temp = NH temp |( z , L ). When finishing the above steps, the new QREQ will be rebroadcast and the status of selected slots will be changed from free to allocate if the NH temp is not null.

When the QREQ package is forwarded from the source node S , it can be regarded as a special case of intermediate nodes. The above steps are performed by replacing y with S , and PATH and NH are null. The procedure select_slot( ) will return, if possible, at least one slot which can be allocated on link ( S , z ). It mainly relies on the slot allocation and reservation rules for directional antennas to do the selection.

For every slot t (1 <  t <  N D ), if the following three conditions hold, slot t is an available free slot at a node.

D1. (RT temp [y , t ]=-1) A (ST temp [ z , t ]=-1)

D2. (H y [ y , w ]=1) A (RT temp [ w, t ]=-1) A (A yw A A y * ф)

D3. (H y [ Z, w ] =1 ) A ( ST temp [ w, t ]=-1) A ( A _z w A A z * Ф)

In the first condition, node y does not receive data packages at slot t . At the same time, node z does not send data packages at slot t .

In the second condition, neighbor node w of node y does not receive data packages at slot t . A _y ^w a A y * ф denotes that the neighbor node w of node y is in the same direction as node z from node y .

In the third condition, neighbor node w of node z does not send data packages at slot t . A zw a AJ * ф denotes that the neighbor node w of node z is in the same direction as node y from node z .

When the destination node D receives the first QREQ package, a path has been formed if two-tuples ( h i , l i ) be belongi _’ ng to the NH and the destiantion node D is the node h i . The path bandwidth is the minimum number of available slots of links in PATH . In other words, the path bandwidth is the number of slots in l I ( b 1 =| l |).

The destination node D has to examine whether this path satisfies the bandwidth requirement of the application. If yes, the required bandwidth is reserved along the path when the QoS Route Response (QREP) package travels to the upstream. This case is the uni-path spatial reused bandwidth reservation for TDMA-based ad hoc networks. Otherwise, the destination node D waits for the next QREQ package until the total bandwidths of discovered paths meet the bandwidth requirement. This case is the multi-path spatial reused bandwidth reservation for TDMA-based ad hoc networks.

As the QREP package travels to upstream, all of the intermediate nodes along the PATH must confirm the reservation (i.e., change status from allocat to reserved). For the first path, the following steps should be conducted for every intermediate node x = hi.

For j=i -2 to i +2 do let ST x [ h j , t ]=1 for the former b 1 slots in l j . For j=i -2 to i +2 do let RT x [ h j , t ]=1 for the former b 1 slots in l j- 1 .

When the source node S receives the QREP package, a path with b 1 slots will be reserved. When the source node S receives multiple QREPs, multiple node-disjoint paths whose total bandwidth can meet the bandwidth requirement will be reserved.

m

£ b i ^ b (5) i = 1

^ . Simulation

In this section, a simulation study is performed by using ns 2 to evaluate the performance of our proposed the spatial reused bandwidth reservation for multi-path QoS routing in TDMA-based ad hoc networks. Suppose that there are 30 nodes randomly placed in 300m x 300m area. The transmission range of the nodes is 100m. The interference range of the nodes is 200m.

Suppose that every connection request is generated with a randomly chosen source-destination pair. The number of date slots in a frame is 32. The data rate of a slot is 512Kbps. The maximal speed of node is 1m/s. The bandwidth requirement for every session is a distribution from 1 to 4 slots.

While evaluating the performance of our proposed the spatial reused bandwidth reservation scheme, we focus on the following parameters: (1) average number of quality of service paths; (2) percentage of date packets received successfully; (3) reservation success ratio.

In our experiment, the simulations are done for three different cases: (1) one antenna; (2) two antennas; (3) four antennas. In the first case, one antenna means that the node has omnidirectional antenna. In the second case and the third case, the nodes have directional antennas.

When the bandwidth requirement is 2 slots, Figure 6 shows the average number of QoS paths as a function of the data arrival rate. The average number of QoS paths range from 1.53 to 1.68 in the omnidirectional antenna case. The average number of QoS paths range from 1.135to 1.25 in the four antennas case. While using directional antennas, our spatial reused bandwidth reservation scheme with four antennas has lower number of QoS paths than the omnidirectional antenna.

When the data arrival rate is 2 messages / second, Figure 7 shows the average number of QoS paths as a function of the bandwidth requirement. When the bandwidth requirement increases, the numbers of QoS paths of three cases increase. The spatial reused bandwidth reservation with four antennas has lower number of QoS paths than the omnidirectional antenna.

In Figure 8, the percentage of successfully received data packages ranges from 38.89% to 19.26% in the one antenna case when the data arrival rate ranges from 2 to 10 messages / second. The highest percentage is obtained in the four antenna case which ranges from 88.12% to 76.46%. It is increasingly easier for the network to acquire data packages as the number of antennas increases.

Figure 9 shows the reservation success ratio between the number of cases when enough slots were available to satisfy the bandwidth requirement and the total number of cases. The bandwidth requirement is assumed to be equal to 4 slots. It is observed that as the number of antennas is increased, the reservation success ratio is increased. This is due to the fact that an increase in the transmission range provided by the directional antenna environment increases the chances of availability of paths with the desired number of slots.

0.8

0.6

0.4

0.2

1 antenna

2 antennas

4 antennas

Data arrival rate(msg/sec)

Figure 9. The reservation success ratio

Е

Z

1 antenna

2 antennas

4 antennas

Data arrival rate(msg/sec)

Figure 6. Average number of QoS paths VS. data arrival rate

4 antennas

V . Conclusion

In this paper, we propose a novel spatial reused bandwidth reservation for multi-path routing in TDMA-based ad hoc networks. The source node tries to discover multiple node-disjoint paths that are capable of providing the desired bandwidth requirement. This novel scheme takes advantage of the significant increase in spatial reuse provided by the directional antenna environment. The simulation results clearly show a significant gain in the performance with a decrease in the number of paths, as well as an increase in the percentage of successfully received packets and reservation success rate.

A CKNOWLEDGMENT

This work has been supported by The Young and Middle-aged Elitists’ Scientific and Technological Innovation Team Project of the Institutions of Higher Education in Hubei Province (No. 200902), Key Scientific Research Project of Hubei Education Department (No. B20091904).

bandwidth requirement (slot)

Figure 7. Average number of QoS paths VS. bandwidth requirement

Data arrival rate(msg/sec)

Figure 8. The percentage of successfully received packages