A Time Slot Reservation in Modified TDMA-Based Ad Hoc Networks with Directional Antennas

Abstract

In this paper, we study the bandwidth reservation issue in wireless ad hoc networks with directional antennas. Providing Quality of Service (QoS) support in the wireless ad hoc networks is one of the topics that have received a lot of attention in recent years. QoS provisioning is needed to support multimedia and real-time application in wireless networks. In the Time Division Multiple Accesses (TDMA) frame, the bandwidth is measured by the number of the data time slots. Control slots in the traditional TDMA frame can be used for transmission of the control packets, rather than the transmission of the data packets. We focus on the problem of how to make full use of slots to transmit data packets and do not affect control packets transmission. The purpose is to improve the time slot utilization rate. Based on our proposed modified TDMA frame, a novel time slot reservation algorithm is presented to achieve maximal available path bandwidth. Directional antennas allow transmission energy to be concentrated on a narrow range along a particular direction, which can significantly increase the data rate. The performance of our scheme is analyzed and implemented. Simulation results show that the proposed scheme performs better.

1. Introduction

Future networks will support all types of traffic. Different traffic types need different Quality of Service (QoS) levels for multimedia services and real-time applications Recently, wireless ad hoc networks have had a significant attraction as a complement of terrestrial networks. However, transmitting the realtime and multimedia data packets in such network environment is a very difficult task. The design of a routing protocol for the provision of QoS in a wireless ad hoc network is a challenging task. Wireless channels must be efficiently utilized to improve the QoS support. The limitation in bandwidth and the power of wireless channels challenge the QoS support for wireless networks. The provision of QoS in wireless networks has attracted a lot of researcher's attention [1–7].

In our previous works [4], we have proposed a multipath QoS routing protocol in traditional Time Division Multiple Accesses (TDMA)-based wireless ad hoc networks. This protocol allows transmitting the real-time data packets between a source node and a destination node, and the route between the source node and the destination node can meet the bandwidth requirement of the application. In order to achieve better bandwidth reservation, many studies focus on time slot reservation in traditional TDMA-based wireless networks [4, 5, 8, 9]. These works suppose that nodes are equipped with the omnidirectional antennas.

In this paper, we study the bandwidth reservation issue in wireless ad hoc networks with directional antennas. The bandwidth reservation in wireless ad hoc networks reserves time slots resource in advance in the phase of transmitting the control packets. There are many applications that depend on transmission in wireless networks such as sports telecast. Directional antennas allow transmission energy to be concentrated on a narrow range along a particular direction, which can bring about a higher signal-to-noise ratio (SNR) at the receivers and thus increases the system throughput. In directional antennas, there are two kinds of beamforming patterns: a lobe pattern and multilobe pattern. In a lobe pattern, only one beam can be used for each transmission. In multilobe pattern, a lot of beams can be used together for one transmission. In the procedure of data transmission, the bandwidth is constrained by the slowest node in the path. Because the transmission in a multilobe splits the transmission power to multiple lobes and then the data rate is decreased by the receiving power, a transmission along a multilobe can bring about a lower data rate than the case of a lobe. There is a challenge in data transmission. If the source node transmits data packets through multiple lobes, it takes less number of transmissions for neighbors to receive the data, but the data rate will be decreased due to the power splitting. On the other hand, if the source node transmits data packets through a lobe, the data rate is high, but it takes more transmissions to cover neighbors. We consider this tradeoff between the number of transmissions and the data transmission rate. The data transmitting problem is an NP-hard problem, and we propose a method to solve the problem.

The problem of our concern is as follows. There is a source node equipped with directional antennas, and a lot of destination nodes that are served by the source node. We suppose that the transmit power of the source node and the beamwidth of directional antennas are fixed. Our object is to find reserved time slots for the source node to destinations such that the paths are optimal. Every path can reserve maximal path bandwidth and minimize the total transmission delay. Our work allows for the adjustment of beam orientations and the use of multilobes. Some research has been done on the topic of data transmitting using directional antennas, such as [10–13]. These research works either use a lobe pattern or use a fixed beam orientation. Some research considers broadcasting scheduling [14], while our research considers the paths from the source node to several destination nodes with reserved time slots. At the same time, our scheme allows using the multilobes and beam orientation adjustment.

In wireless networks, nodes transmit data packages by using an omnidirectional antenna that radiates its power equally in all directions. However, directional antennas allow a node to transmit data in a particular direction. At the same time, a receiving node can focus its antenna on a particular direction. This antenna model provides the following advantages [8]: (1) a smaller amount of power can be used; (2) it can increase the spatial reuse; (3) route has shorter hops and smaller end-to-end delay. In this paper, we present a novel time slot allocation scheme in wireless networks with directional antennas by modifying traditional TDMA frame. We begin from a traditional TDMA frame structure. Then, we propose the modified TDMA frame structure mode. On the basis of it, a bandwidth allocation scheme by using directional antennas is presented.

The time slot reservation problem is an NP-hard problem. We proposed a three phases to solve this problem. Firstly, we use a lobe pattern to all nodes by adjusting the beam orientations. Secondly, we proposed a time slot reservation algorithm for paths from source to destinations. Lastly, based on the results from the first phase and second phase, a multilobes pattern is presented to minimize the total transmission delay. The solution for every phase is optimal. Extensive simulations are conducted to evaluate our proposed method.

This paper is organized as follows. In Section 2, we discuss the related works with our search. Section 3 presents the modified TDMA frame structure mode and the solved problem description. In Section 4, we provide our time slot reservation scheme. Some simulation results are provided in Section 5. Finally, the paper is concluded in Section 6.

2. Related Works

In the wireless networks, how to make use of resources is dependent on the Medium Access Control (MAC) layer protocol. There are two main MAC methods for the wireless networks which are TDMA MAC layer protocol and IEEE 802.11 MAC layer protocol. The 802.11 MAC layer protocol cannot guarantee the real-time communication because it is a contention-based approach. The TDMA MAC layer protocol is a schedule-based approach by reserving time slots for nodes. In order to achieve the bandwidth resource reservation of a selected route in the TDMA-based ad hoc networks, many time slot reservation algorithms have been proposed [8, 15, 16]. These slot reservation algorithms in TDMA-based networks can avoid slot reservation conflict. In this paper, we adopt the TDMA MAC layer protocol. In the traditional TDMA frame structure model, TDMA superframe consists of the control phase and the data phase [8]. The control slots in control phrase are used by transmitting control packets, such as route request packets, route response packets, and route update packets. Every node in the wireless network has its control slot in the control phase. The data slots in data phase are used by transmitting data packets. Figure 1 shows the traditional TDMA frame structure model.

Figure 1

Traditional TDMA frame structure model.

Many QoS routing protocols adopt the TDMA frame structure as the MAC layer. Hsu et al. propose a bandwidth reservation for QoS routing protocol in [15], which supposes that all nodes are equipped with omnidirectional antennas. In [16], Du considers the efficient QoS bandwidth provisioning in hybrid wireless networks. These bandwidth reservation schemes also suppose that nodes use the omnidirectional antennas. The data packages are broadcasted to all neighbor nodes in all directions. In the resource scheduling scheme in [8], Jawhar and Wu suppose that nodes transmit data by using directional antennas. They have presented three time slot allocation conditions. A slot t is free and can be reserved to send data from node x to neighbor y if the following three conditions are satisfied [8]: (1) Node x do not receive data in slot t at any antennas, and neighbor node y do not send data in slot t at any antennas; (2) Neighbors of x do not receive data in slot t, from x where neighbors are in the same direction as receiver y; (3) Neighbors of receiver y do not send data in slot t, from y where neighbors are in the same direction as transmitter x. These time slot allocation conditions can avoid the slot reservation conflict problem.

Figure 2 shows the examples of transmission with directional antennas. According to condition 1, Figure 2(a) shows that node x will not transmit to neighbor y at the slot t, because node x is receiving data at the slot t. According to condition 2, the neighbor node z of the node x is receiving at the slot t in Figure 2(b). Node x will not transmit to neighbor y because y and z are in the same direction of x. In Figure 2(c), node z is sending at the slot t according to condition 3. Node y will not receive from x because x and y neighbor z are in the same direction of y.

Figure 2

Transmission with directional antennas.

There are other slot allocation schemes by using directional antennas technology. Bazan and Jaseemuddin [17] propose the routing and admission controls for wireless mesh networks with directional antennas. Authors study the problem of bandwidth guaranteed routing in contention-based wireless mesh networks with directional antennas. Chen et al. [18] present a shoelace-based QoS routing protocol for mobile ad hoc networks using directional antennas. This scheme offers a bandwidth-based routing protocol for QoS support by using the concept of multipath. Chin et al. [19] propose a novel spatial TDMA scheduler algorithm for transmitting/receiving in wireless mesh networks. Li and Luo [20] present a slot allocation scheme based bandwidth and delay in satellite networks using directional antennas. Feng et al. [21] present a QoS constrained cognitive routing scheme based on directional antennas. Liu et al. [22] consider the topology control for multichannel multiradio wireless mesh networks using directional antennas. Chang et al. [14] propose a minimum delay broadcast scheduling for wireless networks with directional antennas.

The above research works take into account directional antennas. Directional antennas allow transmission energy to be concentrated on a narrow range along a particular direction, which can significantly increase the data rate.

The issue of transmission using directional antennas has been firstly discussed on the physical layer. Sidiropoulos et al. [23] proposed the idea to maximize the smallest signal-to-noise ratio over all the nodes subject to a bound on the transmit power by employing semidefinite relaxation techniques. Similar research joint with power control can be found in [24, 25]. These research works discussed the problem from physical layer without considering the beam scheduling for several transmissions. There are a few studies about transmission with power control using directional antennas at higher layer [10–12]. Aiming to minimize the total transmission delay, Sen et al. [10] presented a two-step solution. In [11], Sundaresan et al. provided two models for power allocating. Equal power split model (EQP) splits the power equally among all the lobes, while asymmetric power slit admits power adjustment among the lobes. Based on the two models, two greedy algorithms were presented to get minimum transmission delay. Zhang et al. [12] resolve the challenge of beam combination discussed in [11] with the similar objective under two models. They achieved an optimal solution under EQP model and showed better performance compared with the methods in [11]. None of the above research works tak the orientation adjustment and multilobe transmission together into account in multipath beam scheduling. Because they all assume that the nodes use fixed beam orientations, the performance improvement of the above algorithms is restricted.

3. Model Improvement

3.1. Modified TDMA Frame Structure Mode

In the traditional TDMA frame model showed in Figure 1, control packets are transmitted in control phrase. Control slots in control phrase are not to be used by transmitting of data packets. In order to save the slots consumption of control packets, we will modify the traditional TDMA frame structure model by deleting the control phrase from the TDMA frame.

Figure 3 shows the modified TDMA frame structure model. Compared with traditional TDMA frame, it reduces the control phrase. Suppose that the control packet is transmitted in the data slot of data phase. This data slot will be reserved if node receives the response control packet. After that, the data packets will be transmitted in the reserved data slot.

Figure 3

Modified TDMA frame structure model.

In the modified TDMA frame model, a TDMA frame only consists of a lot of data slots. Every data slot is used to transmit data packets, control packets, or both, which depends on the node's need. The data packet can be transmitted with the control packet when required. By adopting special slot reservation algorithm with directional antennas in the modified TDMA frame, it can avoid data packets conflict in transmission.

3.2. System Description

The system consists of a source node equipped with directional antennas and a set of destination nodes with directional antennas. The source node wants to send data packets to destination nodes through intermediate nodes. The destination nodes are denoted by $V = {v_{1}, v_{2}, \dots, v_{n}}$ . The beamwidth q is denoted by the angle of directional antennas. The beamwidth q is fixed, and $q < π / 2$ . The source node has fixed transmission power $P_{t}$ . The location of neighbor node $n_{i}$ of the source node is denoted by the $(d_{i}, θ_{i})$ centered from the source node. $d_{i}$ is the distance from the source node to the neighbor node $n_{i}$ , and $θ_{i}$ is the angle of the link from the source node to the node $n_{i}$ from positive horizontal direction. When the source node wants to send data to destination nodes, it tries to find a proper reserved bandwidth path to every destination node such that paths total delay is minimized. When the source node transmits data to neighbor $n_{i}$ by using a lobe whose beamwidth is q, the power received by $n_{i}$ can be computed by using Friis Transmission Formula [26]:

\begin{matrix} P_{i} = \frac{2 π P_{t}}{d_{i}^{w} q}, \end{matrix}

(1)

where w is the coefficient of path loss, which is usually between 2 and 4. Because the beamwidth q is usually narrow and the energy is concentrated, once a node is covered by a lobe, we suppose that receiving power of the neighbor node is determined by its distance to the source. In (1), we suppose that the gain of signal by using directional antennas is

2 π / q

If we use multilobe pattern, we suppose that the power is equally split among the multiple lobes. We assume that there are n transmissions required for the source node to send a data packet to n destination nodes. Let $S_{1}, S_{2}, \dots, S_{k}$ denote k sets of neighbors, and let every set denote one transmission. We suppose that $N_{j}$ denote the number of lobes on jth transmission, and the receiving power of neighbour node $n_{i} \in S_{j}$ satisfies the following formula:

\begin{matrix} p_{(i, j)} = \frac{P_{i}}{N_{j}}, \end{matrix}

(2)

which means that the transmit power for each lobe in multilobes mode is

1 / N_{j}

. We assume that the maximum available bandwidth

B_{(S, i)}

of neighbor node

n_{i}

to receive packet from source node in jth transmission.

B_{(S, i)}

is determined by the received signal-to-noise ratio (SNR) of node

n_{i}

, which can be computed by the following formula:

\begin{matrix} B_{(S, i)} = f ({SNR}_{(S, i)}), \end{matrix}

(3)

where

f ()

is a mapping function from SNR to bandwidth of node

n_{i}

and the following formula is computed:

\begin{matrix} {SNR}_{(S, i)} = \frac{P_{(S, i)}}{E}, \end{matrix}

(4)

where E is the environmental signal noise. According to formula (3) and formula (4), we can get the following formula:

\begin{matrix} B_{(S, i)} = f (\frac{P_{(S, i)}}{E}), \end{matrix}

(5)

which means that the bandwidth of link from the source node S to

n_{i}

n_{i}

is a neighbor node of S. In data transmission duration, the bandwidth of a path from the source node S to the destination node

v_{i} \in V

is determined by the lowest bandwidth of links in path. Let

B_{path}

denote the path bandwidth of a path from S to node

v_{i}

. Suppose that the

B_{(i, j)}

is the bandwidth of the link

(n_{i}, n_{j})

in the path. The Following formula can be calculated:

\begin{matrix} B_{path} = \min_{n_{i} n_{j} \in path} {B_{(i, j)}}, \end{matrix}

(6)

which means that the path bandwidth is the lowest link bandwidth of the path.

n_{i} n_{j}

denotes a link from node

n_{i}

to node

n_{j}

in the path from the source node S to the destination node

v_{i}

. The delay

l_{(i, j)}

for the link

(n_{i}, n_{j})

is calculated by the formula where L is the size of a data packet:

\begin{matrix} l_{(i, j)} = \frac{L}{B_{(i, j)}} . \end{matrix}

(7)

The delay $l_{path}$ of a path is calculated that formula (8), which means that the delay of a path is the sum of all the link delay of the path. If the source node can receive route response packets from n destination nodes, the total delay of multiple paths can be described as in formula (9):

\begin{matrix} l_{path} = \sum_{n_{i} n_{j} \in path} l_{(i, j)} = \sum_{n_{i} n_{j} \in path} \frac{L}{B_{(i, j)}}, \end{matrix}

(8)

\begin{matrix} D = \sum_{1 \leq i \leq n} l_{{path}_{i}} . \end{matrix}

(9)

We will study how to adjust orientations of directional antennas for source node to form a set of multilobes such that the total transmission delay defined in (9) is minimized. The minimum delay broadcast scheduling problem is proved to be an NP-hard problem [14], and we will prove that the minimum delay scheduling of slot reservation in multiple paths from the source node to multiple destination nodes is also an NP-hard problem. We prove the theorem according to the weighted set cover problem, a well-known NP-hard problem [27]. The weighted set cover problem is described as follows. Let $A = {1, 2, \dots, n}$ express a set of n elements. B consists of finite sets $B_{1}, B_{2}, \dots, B_{n} \subseteq A$ with weight $w_{j}$ for $B_{j} \in B$ . We denote $\cup (B_{j} : 1 \leq j \leq n)$ by A. The objective is to find a subset of B that covers all elements in A with a minimum weight. According to the weighted set cover problem, let every element $i \in A$ correspond to the destination node $v_{i}$ . $B_{j}$ denotes the set of nodes covered by one transmission and $w_{j}$ denotes the corresponding transmission delay. Our problem is to find an optimal set of transmissions to cover all destinations to minimize the total transmission delay, which is just to find a subset of B with minimum weight in weighted set cover problem. General greedy approach for weighted set cover problem cannot be used for our method. We will use a three-phase method to solve the problem.

3.3. A Three Phase Scheduling Method

The problem we study is a complicated optimization problem. The complexity of this problem comes from the following three concurrent cases. (1) Which subset of neighbor of the source node may be covered by a lobe? By adjusting the beam orientation, the bandwidth of this lobe varies because the bandwidth is constrained to the smallest bandwidth of the neighbors in this lobe. (2) Which subset of lobes may form a multilobe? Once more lobes form a multilobe, the number of transmissions reduces. However, the bandwidth of transmission reduces due to the power scatter. Once less lobes form a multilobe, the bandwidth for each transmission increases and the number of transmissions increases. (3) Which lobes may be used by the nodes in the path such that the available path bandwidth is maximized?

Based on the above three subproblems, we present a three-phase scheduling method. In the first phase, we only adopt a lot of lobes to cover all neighbors of the source node such that the transmission delay is minimized. In the second phase, we group multiple lobes to form multilobes to minimize the delay. Figure 4 shows an example. We suppose that the size of the data packet is 1 Mb and the bandwidth of the path is 9 Mbps. Suppose that there are two paths from the source node to two destinations which the hop number is two. If all nodes use omnidirectional antennas to transmit the data packets, the transmission delay is 0.22 s which is the result of 1 divided by 9 times 2. By the end of the first phase, two lobes are adopted, which means that the source node can transmit two times to cover two neighbors to transmit data packets to two destinations. The total delay is 0.15 s. After the second phase, the source needs one transmission for covering two neighbors and the total delay for two destination nodes is 0.11 s. In the third phase, we adopt time slot scheme described in Section 4. The total delay for two destination nodes is 0.108 s, and the total bandwidth is 36 Mbs.

Figure 4

An example of three phase method.

4. Our Time Slot Reservation Scheme

In wireless networks, node mobility is handled by taking into account the slot allocation modes of nodes in two hops area when requesting to reserve slots for multimedia application. Therefore, it can avoid collisions with the neighbors in two hops when a node moves. When a node starts to move, the nodes that will become its neighbors are those which were its two-hop neighbors. In that case, there is no collision because these neighbors have reserved different data slots. There are three types of control packets which are route request packet, route response packet, and update packet. The route request package is used to search route and request slot allocation. The route response package is used to confirm the route and reserve the allocated slots. The update packet is used to inform the neighbors in the two-hop area about the reservation status change.

In the wireless ad hoc networks with directional antennas, we suppose that each node is equipped with directional antennas. It is assumed that a multibeam antenna arrays (MBAA) is capable of broadcasting by adjusting the beam width [8]. Therefore, in order to consider antennas' beam direction for the slot allocation-based directional antennas, node mobility issue tackling is based on reserving slots in the two-hop neighboring and corresponding angular directions of antennas.

We suppose that each node maintains a slot reservation table which contains four columns. The first column means the node ID that has reserved a time slot; the second column presents the number of reserved slots in the modified TDMA frame; the third column records reserved node which is a direct neighbor or a two-hop neighbor or the node itself (expressed by 1, 2, or 0). The fourth column indicates the antenna direction of reserved slot. A node can select a slot which is reserved by its two-hop neighbors when the antenna directions of slot are not the same.

In our proposed time slot allocation scheme-based directional antennas, we consider the two-hop neighbor's slot reservation and antenna directions. The time slot allocation scheme can be described with Algorithm 1.

Algorithm 1

if (intermediate node i receives a route request package at the first time)

{ do {

if (direction from node i to the next hop is similar to the direction of reserved slot in two-hop area)

it chooses a free slot for node i.

else it chooses the slot which is reserved in two-hop area with different direction.

} while (no collision is detected in the selected slot)

if (number of selected slots at node i satisfies the bandwidth requirement for the application)

it forwards a request package in the allocated slot after node i and slots are added to

the reservation table.

else node i discards the route request package.

} end if

After the node selects slots and meets the bandwidth requirement, the route request package will be forwarded to neighbors in the allocated slots. The allocated slots are recorded in the slot reservation table of node i, but the status of the slot is allocated not reserved. When the node i receives a route response package, following slot reservation, Algorithm 2 is described.

Algorithm 2

if (node i receives a route response package at the first time)

{ do {

it modifies the status of slots from allocated to reserved in the reservation table, and it adds

the antenna direction of reserved slot to the reservation table;

it broadcasts the update packet to neighbors of node i in reserved slot;

} while (there is an allocated slot in reservation table)

} end if

When the intermediate node i reserves the slots and broadcasts the update packet, neighbors j precedes the operation shown in Algorithm 3.

Algorithm 3

if (node j receives an update packet from its neighbor i)

{ it adds a row to its reservation table, which indicates that neighbor node i has reserved slots at

antenna direction;

it informs its neighbors about the updates in its reservation table;

} end if

When the source node receives the several route response packages from the same destination, it chooses the smallest delay path according to formula (8) in Section 3.2. After determining all paths to all destination nodes, the source node starts to transmit data packets in reserved slots along the selected paths because the reserved smallest delay paths has been found. The nodes in other reserved paths release reserved slots after receiving route release packets from the source node. The intermediate nodes forward the data packets in reserved slots once they receive the data packets. When the intermediate node does not receive a data packet in the reserved slot, it means that the packet conflicted due to mobility of nodes. In order to avoid the packet conflict due to the mobility of the nodes, Algorithm 4 is performed.

Algorithm 4

if (intermediate node j does not receive a data packet from its neighbor i in reserved slot)

{ it deletes a row, which indicates that the node i and corresponding reserved slots will be deleted

from its reservation table;

it deletes a row, which indicates that the node j itself and corresponding reserved slots will be

deleted from its reservation table;

it informs its neighbors about the updates in its reservation table by broadcasting the update

packets;

neighbors perform the Algorithm 3, which is modified to delete a row in reservation table;

} end if

If the source node wants to transmit the data packets to multiple destination nodes, it chooses the smallest delay multipath according to formula (9) in Section 3.2. In order to describe the details of the time slot allocation and reservation scheme, we will start by explaining the one-hop functioning. Then, node behavior in package conflict case will be described. Finally, we will analyze the two-hops functioning. Supposing that the node in a dense ad hoc network will find neighbors in each $2 R$ area, where R is a minimum transmitting range of the nodes.

4.1. One-Hop Functioning Case of the Slot Allocation and Reservation

The principle of our slot allocation and reservation approach is based on the modified TDMA frame structure model for the subsequent data transmission. In the traditional slot reservation algorithm [18], there is no obvious difference between slot allocation and slot reservation. In our scheme, when the node receives the route response package, allocated slots will be changed to reserved status. If the node does not receive the route response package in the following frames, allocated slots will be changed to free status in order to free more slots for other route request packages.

In the reservation table, we add a row without antenna direction information when the node receives a route request packet and meets the conditions of Algorithm 1. The selected slots are added to the reservation table, but antenna direction information is not added to the table. The reason is that these selected slots are allocated status. Only when the node receives a route response package, the status of selected slots are changed from allocated to reserve. Therefore, the antenna directions of reserved slots are added to the reservation table.

If the node that has allocated slots does not receive a route response package in subsequent three frames, the status of selected slots is changed from allocated to free. In other words, the row without antenna direction information will be deleted from the reservation table. If the node that has been reserved slots does not receive a data packet in reserved slots of subsequent frames, the status of reserved slots will be changed to free. Therefore, the row with antenna direction information will be deleted too. The slots with free status will be ready for the subsequent route request packets.

In order to illustrate the one-hop functioning case of the allocation and reservation scheme-based directional antennas with four beams, we suppose that there are four nodes in Figure 5. At first, the slot reservation tables of four nodes are empty, which means that all slots are free in four nodes' neighborhood. The line between two nodes indicates the neighboring. Table 1 shows the reservation table of node, which contains node ID, reserved slots set, direct neighbor node, and antenna direction. When node N1 wants to transmit data packets to neighbor node N4, the following steps will occurr. In this example, we focus on the allocation and reservation of the free slot 1 for transmission from N1 to N4, which are one-hop neighbor.

Table 1

Reservation table of node N1.

Node ID

Slots

Direct node

Direction

Figure 5

Neighboring nodes in one-hop functioning case.

Step 1 (during the slot 1 of the first modified TDMA frame). N1 starts to broadcast a route request packet in free slot 1. After neighbors N2 and N4 receive this request packet, these nodes add a row to their reservation tables. The triple (N1, S1, 1) is added to the reservation tables of N2 and N4. The triple (N1, S1, 0) is added to the reservation table of N1. It is notable that the antenna direction is not added to the reservation tables. The reason is that the status of slot 1 is allocated.

Step 2 (during the slot 2 of the first modified TDMA frame). N4 starts to broadcast a route response packet in free slot 2. After neighbors N1 and N3 receive this route response packet, node N1 adds antenna direction of reserved slot to the reservation table. The reservation table contains a row (N1, S1, 0, 0), which means that N1 reserves slot 1 at the horizontal 0 degree direction.

Step 3 (during the slot 1 of the second modified TDMA frame). In the subsequent modified TDMA frame, N1 transmits data packet during the slot 1. The update packet can be piggybacked with the data packet in the slot 1 of the second TDMA frame. After neighbors N2 and N4 receive this update packet, they add the antenna direction to their reservation tables. In other words, a row (N1, S1, 1, 0) records the slot reservation information of neighbor N1.

If N1 want to transmit data packets to neighbor N2 after N1 transmitted data packets to neighbor N4, slot 1 in the reservation table will be selected again. The reason is that 90 degree direction of the link (N1, N2) is different from 0 degree direction of reserved slot 1 for link (N1, N4) when using directional antennas with four beams. Therefore, a row (N1, S1, 0, 90) is added to the reservation table of N1, which means the slot 1 is reserved two times in two different antenna directions. N1 will transmit data packets to two neighbours in the same slot without conflict with each other because of the use directional antennas. If using omnidirectional antennas, N1 cannot transmit data packets to two neighbours in the same slot. N1 must select a free slot to reserve for the new transmission in order to avoid slot reservation conflict. From the third modified TDMA frame, node N1 can transmit data packets to N2 and N4.

Step 4 (during the slot 1 of the fourth modified TDMA frame). Suppose that N2 and N4 find that they do not receive data packets during the slot 1. There is a transmission break problem due to mobility of node, which brings about N2 and N4 are not one-hop neighbour of the node N1. In this case, N2 and N4 delete a row in their reservation tables, which means that the status of slot 1 is changed from reserved to free. The free slot 1 may be allocated for other route request packets in the subsequent frame.

4.2. The Collision Case

A collision case will be found by the neighbor nodes which broadcast the route request packets. The neighbors will notice that reservation is canceled when no data packet arrives in the reserved slot of the subsequent modified TDMA frame. In order to decrease the packet collision instances, the node which has caused a collion will not reselect the same slot to broadcast a route request packet. In order to illustrate the collision case, we consider the following case shown in Figure 5. We suppose that the modified TDMA frame contains 10 data slots, and slot 1 was, respectively, reserved by node N1 at horizontal and vertical directions for transmitting data packets to neighbour N4 and N2. When two neighboring nodes N2 and N3 broadcast the route request packets during the same slot 2 after N1 starts to transmit data packets, the following steps will be performed.

Step 1 (during the slot 2 of the first frame after N1 starts to transmit data packets). There is a collision when N2 and N3 broadcast route request packets during the same slot 2. Because N2 and N3 send request packets in the same time, a collision is found and the slot allocation algorithm is not performed by the nodes N2 and N3 as well as their neighbor N1 and N4. Node N2 calculates the slot ID from which it will search a free slot to use for sending route request packet. The slot ID is calculated according to the total number of slots in modified TDMA frame modulo the ID of node. In Figure 5, free slot 2 is allocated to node N2, because 10 modulo 2 equals 0. The first free slot that starts from 0 is slot 2, because slot 1 has been reserved for link (N1, N2).

Step 2 (during the slot 3 of the first frame after N1 starts to transmit data packets). Node N3 calculates the slot ID from which it will search a free slot to use for sending route request packet. The free slot 3 is allocated to N3, because 10 modulo 3 is equal to 1. The first free slot that starts from slot 1 is slot 3, because slot 1 and slot 2 have been reserved. Nodes N2 and N3, respectively, broadcast the route request packets in different slots. Therefore, there is no collision case between N2 and N3.

4.3. Multihops Functioning Case of the Slot Allocation and Reservation

It is not sufficient to consider the slot allocation and reservation in one-hop neighboring when the route request packet traverses multiple hops in mobile ad hoc networks. If a two-hop neighbor node starts to move suddenly, it may come to a 1-hop neighbor node or three-hop neighbor. The reservation information of the two-hop neighbor node must be taken into account. The two-hop neighbors may reserve the same slot with the source node before becoming a one-hop neighbor. Therefore, the collision can take place because neighboring nodes reserve the same slot. The slot reservation table must consider the reservation of all two-hop neighboring nodes. In order to illustrate the reservation procedure in the multiple hops functioning, we suppose that there are eight nodes in Figure 6. Initially, node N1 has reserved the slot 1 for the link (N1, N4) at the horizontal direction. In this example, we will describe the following steps that will occur when node N3 needs to transmit data packets to node N8.

Figure 6

Neighboring nodes in multiple-hops functioning case.

Step 1 (during the slot 2 and slot 1 of the modified TDMA frame). Reservation table of node N1 is shown in Table 2. Node N3 sends a route request packet to neighbor node N7 during the slot 3. If all nodes in ad hoc network do not move, N3 will reserve slot 1. In order to avoid the conflict with the node 1 due to the node mobility, N3 selects a free slot 2 to send the route request packet. N7 sends the route request packet to neighbor node N8 during the free slot 1. We can allocate the same slot to N7 with the three-hop neighbor node N1 in Table 3.

Table 2

Reservation table of node N1.

Node ID	Slots	Direct node
N1	S1	0
N2	S3	1
N3	S2	2

Table 3

Reservation table of node N3.

Node ID	Slots	Direct node
N1	S1	2
N2	S3	1
N3	S2	0
N7	S1	1

Step 2 (during the slot 3 and slot 4 of the first modified TDMA frame). Node N8 sends a route response packet to neighbor node N7 during the slot 3. N7 forwards the route response packet to neighbor node N3 during the free slot 4. The bold font in reservation tables of nodes N1 and N3 shows that the added information is after receiving the response packet and update packet.

5. Simulation

In order to verify and analyze the performance of our scheme, simulation experiments have been conducted. Traditional slot reservation approaches adopt TDMA frame as MAC layer, but our slot allocation and reservation approach is based on the modified TDMA frame. TDMA protocol class in NS 2 is modified as removing precursor MAC protocol class in our simulation. In the TDMA class declaration, remove the *tdma_preamble_statement. The physical interface for each node binds a directional antenna and adds support for multiple interfaces by using TENS [28]. We compare our scheme with a traditional slot reservation approach that uses directional antenna [18], which is called traditional scheme. We adopt (2) in Section 3.2 to compute the SNR of nodes. We use a simulation program focusing on three performances: the maximum end-to-end delay, the percentage of control packets, and the percentage of data packets received successfully.

Simulation parameters are shown in Table 4. The nodes are allocated in an area of 300 m × 300 m. Number of slots required for each session is a random number with a uniform distribution in the range from 1 to 4 slots (1 to max_b), where max_b means the max bandwidth requirement. The transmission range of each node is 115 m. The number of data slots in a frame is 30 and the number of sessions is 20. The first performance is the maximum end-to-end delays in the busiest network case, in which all the nodes have reserved slots in the modified TDMA frame to transmit real-time data packets.

Table 4

Simulation parameters.

Name of parameter	Value of parameter
Network area	300 m × 300 m
Number of nodes	25~225
Transmission range	115 m
Bandwidth	2 Mb/s
Data packet size	512 bytes
Number of data slots	30
Number of sessions	20
Average message length	100 MB
MAX_SLOT_RES_TIME	10980 ms
MAX_SLOT_ALLOC_TIME	1350 ms
MAX_B	4 slots

Figure 7 shows the maximum end-to-end delay value when increasing the number of nodes in network. We fix the beamwidth to 36 degrees, and the transmit power is 20 dBm. We notice that the maximum end-to-end delay using our scheme is stable and it stays 62 ms when the number of nodes is above 36 $(6 \times 6)$ . However, the delay of the traditional slot reservation approach continues to increase when the number of nodes increases. The reason is that the control packets in our scheme are incorporated in the data packets. More time slots can be reserved in our scheme, and the end-to-end delay will not increase obviously. We notice also that our scheme offers better delay in dense networks (more than 100 nodes).

Figure 7

The maximum delay of two schemes.

The second performance compared is the percentage of the control package length of the frame. Figure 8 shows the comparison between our scheme and the traditional slot reservation scheme. With the increase of number of nodes, the traditional scheme has more control packets. The reason is that each node in the network is allocated a control slot for transmitting control packets. Our scheme has a lower percentage of control packets of the frame, which is stable and lower than the traditional scheme. This is due to the combination of the control packets with the data packets. Control packets are not transmitted in control slots in our scheme.

Figure 8

Percentage of the control package in the frame.

Several performance measures have been computed when the traffic rate is varied in Figure 9. The following simulations are done for two different cases: (1) 2 antennas (angle of overage is 180 degrees) and (2) 4 antennas (angle of overage is 90 degrees). The measured parameter is the overall percentage of packets received successfully. In Figure 9, it can be observed that the average overall percentage of successfully received data packets decreases when the traffic rate increases. The overall percentage of packets in four antennas case is higher than that of the two antennas case. The simulation shows that more packets can be transmitted successfully by using more directional antennas.

Figure 9

Percentage of packets received successfully.

In following simulations, we use formula (4) of Section 3 to compute the SNR of nodes. In the fourth example, we suppose that n destinations are uniformly distributed in Figure 10(a). We fix the beamwidth to 36 degrees, and the transmit power is 20 dBm. It can be observed that with the increase of the number of destination nodes, our scheme outperforms the traditional scheme, with a delay reduction of about 18%. Figure 10(b) shows the comparison of two schemes with increasing transmit power. We suppose that the beamwidth is 36 degrees and the number of destination nodes is 30. It can be seen that our scheme always performs the traditional scheme with about 40% when transmit power is 12 dBm.

Figure 10

Simulation delay result for scenario of uniformly distributed.

In Figure 11, we compare the overall percentage of packets received successfully when the bandwidth requirement is varied. It can be observed that with the increase of bandwidth requirement, the overall percentage of packets received successfully decreases when the beamwidth is 36 degrees and the transmit power is 20 dBm. Our scheme has higher percentage of packets received because more route request packets can be received.

Figure 11

Overall percentage of packets received successfully.

In the final experiment, we compare the result of our scheme and the method used in [12] called DP-RQP, which uses directional antennas. Figure 12 shows the result of comparison of the two methods with increasing the bandwidth requirement. The beamwidth is 36 degree and the transmit power is 20 dBm. The number of destination nodes is 30. Our scheme has lower delay than DP-RQP method, because our scheme adopts three phases to decrease the transmission delay.

Figure 12

Simulation delay result for different bandwidth requirements.

6. Conclusion

In this paper, we propose a novel time slot reservation scheme in modified TDMA-based Ad Hoc networks using directional antennas. Our scheme is based on reducing the bandwidth consumption of control packets by deleting the control phase of the traditional TDMA frame. The control packets are incorporated with the data packets. It also takes advantage of the significant increase in spatial reuse provided by using directional antennas. We propose a three-phase method to decrease the delay. Simulation results show that the time slot reservation scheme using directional antennas can improve the delay and the percentage of control packets. It also increases the percentage of successfully received packets, especially when the number of directional antennas increases. Future work includes analyzing the effect of slot reservation on routing protocol and optimizing the performance of slot reservation scheme.

Footnotes

Acknowledgments

This work has been supported by the National Natural Science Foundation of China under no. 60772088, Young and Middle-aged Elitists' Scientific and Technological Innovation Team Project of the Institutions of Higher Education in Hubei Province (no. T200902), Yong Reserch Project of Hubei Education Department (no. Q20112205), and Key Reserch Project of Hubei Education Department (D20121903, D20121904).

References

Chen

Heinzelman

W. B.

QoS-aware routing based on bandwidth estimation for mobile ad hoc networks

IEEE Journal on Selected Areas in Communications 2005 23 3 561 572

2-s2.0-15244356110

10.1109/JSAC.2004.842560

Kamruzzaman

S. M.

Kim

Jeong

D. G.

An energy efficient QoS routing protocol for cognitive radio ad hoc networks

Proceedings of the 13th International Conference on Advanced Communication Technology (ICACT '11)

February 2011

344 349

2-s2.0-79955687741

Almobaideen

Hushaidan

Sleit

Qatawneh

A Cluster-based approach for supporting QoS in Mobile Ad Hoc networks

International Journal of Digital Content Technology and Its Applications 2011 5 1 1 9

2-s2.0-79953694726

10.4156/jdcta.vol5.issue1.1

Sun

Luo

Joint topology-transparent scheduling and multipath QoS routing in MANETs

Proceedings of the 8th IEEE International Symposium on Dependable, Autonomic and Secure Computing (DASC '09)

December 2009

Chengdu, China

767 771

2-s2.0-77950564644

10.l09/DASC.2009.153

Wang

Lee

A time slot assignment scheme for multi-path QoS multicast routing in mobile ad hoc networks

Proceedings of the International Computer Symposium (ICS '10)

December 2010

Tainan, Taiwan

529 534

2-s2.0-79851486813

10.1109/COMPSYM.2010.5685454

Sun

Song

Gui

Jia

Mobility entropy-based clusterhead selection algorithm for Ad Hoc networks

Journal of Convergence Information Technology 2011 6 10 49 55

2-s2.0-80355145127

10.4156/jcit.vol6.issue10.7

Karam

F. W.

Jensen

A survey on QoS in next generation networks

Journal of Advances in Information Sciences and Service Sciences 2010 2 4 91 102

Jawhar

Resource scheduling in wireless networks using directional antennas

IEEE Transactions on Parallel and Distributed Systems 2010 21 9 1240 1253

2-s2.0-77955231672

10.1109/TPDS.2009.171

Kouroshnezhad

Zokaei

Yeganeh

Slot reservation demand assignment multiple access control protocol for signalling of telephony traffic via geo satellite

Proceedings of the 10th International Conference on Advanced Communication Technology (ICACT '08)

February 2008

693 698

2-s2.0-44249096850

10.1109/ICACT.2008.4493855

10.

Sen

Xiong

Choudhury

R. R.

Link layer multicasting with smart antennas: no client left behind

Proceedings of the 16th IEEE International Conference on Network Protocols (ICNP '08)

October 2008

53 62

2-s2.0-67249099811

10.1109/ICNP.2008.4697024

11.

Sundaresan

Ramachandran

Rangarajan

Optimal beam scheduling for multicasting in wireless networks

Proceedings of the 15th Annual ACM International Conference on Mobile Computing and Networking (MobiCom '09)

September 2009

205 216

2-s2.0-70450227316

10.1145/1614320.1614343

12.

Zhang

Jiang

Sundaresan

Rangarajan

Zhao

Wireless data multicasting with switched beamforming antennas

Proceedings of the IEEE INFOCOM Mini-Conference

April 2011

Shanghai, China

526 530

2-s2.0-79960866014

10.1109/INFCOM.2011.5935219

13.

Chang

Liu

Zhang

Jia

Xie

Minimum delay broadcast scheduling for wireless networks with directional antennas

Proceedings of the 54th Annual IEEE Global Telecommunications Conference (GLOBECOM '11)

December 2011

2-s2.0-84857207009

10.1109/GLOCOM.2011.6133964

14.

Chang

Liu

Jia

Zhou

Routing and transmission scheduling for minimizing broadcast delay in multi-rate wireless mesh networks using directional antennas

Wireless Communications and Mobile Computing 2012

10.1002/wcm.2318

15.

Hsu

Sheu

Tung

An on-demand bandwidth reservation QoS routing protocol for mobile ad hoc networks

Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing

June 2006

198 207

2-s2.0-33845382644

10.1109/SUTC.2006.39

16.

Efficient quality-of-service provisioning and communications in hybrid wireless networks

Proceedings of the 7th International Conference on Wireless Communications, Networking and Mobile Computing

September 2011

Istanbul, Turkey

keynote talk

17.

Bazan

Jaseemuddin

Routing and admission control for wireless mesh networks with directional antennas

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '09)

April 2009

1 6

2-s2.0-70349182593

10.1109/WCNC.2009.4917955

18.

Chen

Y. S.

Hsu

C. S.

Jan

S. J.

A shoelace-based QoS routing protocol for mobile ad hoc networks using directional antenna

Wireless Personal Communications 2010 54 2 361 384

2-s2.0-77953611457

10.1007/s11277-009-9730-3

19.

Chin

Soh

Meng

A novel spatial TDMA scheduler for concurrent transmit/receive wireless mesh networks

Proceedings of the 24th IEEE International Conference on Advanced Information Networking and Applications (AINA '10)

April 2010

481 488

2-s2.0-77954339932

10.1109/AINA.2010.13

20.

Luo

A bandwidth allocation scheme based on QoS in satellite networks using directional antennas

Proceedings of the 7th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM '11)

September 2011

1 4

2-s2.0-80054924306

10.1109/wicom.2011.6040228

21.

Feng

Ding

Liu

Gui

Zhou

A QoS constrained cognitive routing algorithm for ad hoc networks based on directional antenna

Proceedings of the International Conference on Wireless Communications and Signal Processing (WCSP '11)

November 2011

2-s2.0-84555195077

10.1109/WCSP.2011.6096897

22.

Liu

Jia

Zhou

Topology control for multi-channel multi-radio wireless mesh networks using directional antennas

Wireless Networks 2011 17 1 41 51

2-s2.0-79951726405

10.1007/s11276-010-0263-1

23.

Sidiropoulos

N. D.

Davidson

T. N.

Luo

Transmit beamforming for physical-layer multicasting

IEEE Transactions on Signal Processing 2006 54 6 I 2239 2251

2-s2.0-33744542350

10.1109/TSP.2006.872578

24.

Lozano

Long-term transmit beamforming for wlreless multicasting

Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (IICASSP '07)

April 2007

III417 III420

2-s2.0-34547525363

10.1109/ICASSP.2007.366561

25.

Matskani

Sidiropoulos

N. D.

Tassiulas

On multicast beamforming and admission control for UMTS-LTE

Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (IICASSP '08)

April 2008

2361 2364

2-s2.0-51449087742

10.1109/ICASSP.2008.4518121

26.

Cross

F. B.

Smart Antennas for Wireless Communications 2005

New York, NY, USA

McGraw-Hill

27.

Feige

A threshold of In n for approximating set cover

Journal of the ACM 1998 45 4 634 652

2-s2.0-0032108328

28.

The Enhanced Network Simulator (Version 1. 2), http://www.cse.iitk.ac.in/users/braman/tens/