Sage Journals: Discover world-class research

Abstract

Routing metric is very important for performance of wireless ad hoc sensor networks. ETX and ETT routing metrics cannot accurately estimate the average transmission time since they do not take back-off scheme of IEEE 802.11 in Mac layer into account. We present a new available transmission time (ATT) routing metric based on IEEE 802.11 DCF, which considers available link bandwidth and also takes physical transmission rates into account. A plugin for OLSR routing protocol daemon is implemented on Linux platform, and experiments are taken to compare ATT with ETX and ETT. Our results show that the ATT metric has the lowest packet loss rate and the lowest jitter rate among the analyzed metrics. ATT also outweigh other two metrics in the network performance, so it is the most appropriate for wireless ad hoc sensor networks.

1. Introduction

Wireless ad hoc sensor network combines advantages of both wireless LAN and mobile ad hoc networks. It has become the key technology of next generation wireless networks [1]. IEEE 802.11 protocol is widely used as standard. It supports fixed infrastructure and ad hoc operation modes. Wireless nodes working in Ad Hoc mode, can construct routing in multihop collaborative manner. Wireless ad-hoc networks support multihops communication between access points to improve communication coverage and ensure connectivity. Thus, power consumption and mobility is not a major problem, routing protocols generally concern about the link quality [2–4].

Appropriate routing metric is significant for the performance of routing protocols. In [5], expected transmission count (ETX) routing metric is proposed. It considers the impact of links' packet loss rate on network performance. To further improve the performance of routing protocols, expected transmission time (ETT) is proposed in [6], which is based on the ETX and takes the influence of data transmission rate into consideration. Experiments show that ETT outweighs ETX [7] in network performance. Considering the link-competitive interference of IEEE 802.11 DCF, a new routing metric of expected data rate (EDR) is proposed in [7]. Reference [8] gives a theoretical analysis on various routing metrics and proposes several essential requirements for routing metric design. On the basis of EDR, a new routing metric which comprehensively take interpath and intrapath interference as well as channel diversity is presented and validated by simulation in [9]. In [10], the ETT-routing metric for open link state routing (OLSR) is implemented and tested in wireless test beds. Test results show that ETT is better than ETX. Reference [11] studies the MAC-aware link quality metrics and proposes a new wireless link quality metric of estimated channel occupancy Time (ECOT) which focus on improving network throughput.

IEEE 802.11 distributed coordination function (DCF) is widely used as the medium access control mechanism for wireless networks. Researches on routing metric usually do not consider the exponential back-off strategy in IEEE 802.11 MAC layer [12], which influences such performance as throughput, jitter, packet loss rate, and time delay. Thus, ETT-based routing metrics are not effective to assess the average time of packets transmission and reflect the available link bandwidth. OLSR may choose one 1-hop low quality links not two-hop high quality ones. Therefore, we propose a new kind of routing mechanism based on available transmission time measurement. Besides, in the platform of embedded Linux platform, we implemented an extension OLSR protocol [13] using ETX, ETT, and ATT.

2. Routing Metric

2.1. Expected Transmission Count

The ETX routing metric [5] is associated with packet loss rate. It is defined as the transmissions or retransmissions count required to successfully delivering a packet over wireless link. The ETX of a path is the sum of the ETX of each link along the path. ETX takes into account the possibility that link loss rates are asymmetric to calculate packet loss rate for bidirectional links. The probability that packets from senders to receivers are transmitted without errors is called forward delivery ratio and represented by $d_{f}$ . The probability of reverse link from receiver to sender is also calculated. It is called as reverse delivery ratio $d_{r}$ and corresponds to the ACK packets that will be sent to acknowledge the original sending packet. The multiple of $d_{f} \times d_{r}$ reflects the probability that a packet is sent correctly, and its ACK packet is received successfully. ETX can handle asymmetric link problem and prefer to shorter routes.

In order to calculate forward delivery ratio, probe package is sent by wireless node. Finally, ETX is defined as in the following equation:

ETX = \frac{1}{d_{f} \times d_{r}} .

(1)

ETX contributes to achieving maximization of link throughput. But the ETX cannot distinguish from different link bandwidths, packet loss rates of data frames with different sizes. Besides, it does not support multirate.

2.2. Expected Transmission Time

Expected transmission time [14] is used to estimate the time cost of sending a packet through link successfully. In order to calculate the link packet loss rate and bandwidth for forward and reverse link, respectively. The same method of broadcasting probe frame as ETX is used to detect packet loss rate. Link bandwidth is measured by packet-pair technology. ETT can be defined as in the following equation:

ETT = ETX \times \frac{S}{B},

(2)

where S denotes packet size, and B means link bandwidth respectively. Nodes broadcast packet pair of different sizes to measure each link's bandwidth. Neighboring nodes immediately calculate the time interval of packet pair after receiving them and feedback it to the senders. The bandwidth is calculated as in the following equation:

B = \frac{S_{L}}{\min_{1 \leq i \leq n} d_{i}},

(3)

where, and

S_{L}

denotes the biggest probe packet pair.

d_{i}

denotes the time interval between receiving packet pair.

The advance of ETT is that it takes the link bandwidth into account. Suppose that there are N destination nodes in the wireless network, the source node could use back-to-back (unicast) packet-pair probings. This requires $O (N^{2})$ probings. The probing overhead is $O (N^{2})$ . If broadcast is available, then the time complexity of broadcasting HELLO message is $O (N)$ . Therefore, link bandwidth estimation will cause certain overhead.

3. ATT Routing Metric

In order to address the existing problems that ETX and ETT do not consider the MAC layer features, an available transmission time routing metric based on link bandwidth availability is proposed. This metric considers the relationship between the lost packet quality and the characteristics of 802.11 DCF. ATT is defined as the time of transmission required to successfully deliver a packet over the available bandwidth. The new metric is defined in the following equation:

ATT = \frac{1}{r_{B}} \times \frac{S}{B} .

(4)

Here, $r_{B}$ is bandwidth availability which denotes the time ratio of successfully transmitting packets to responding retransmissions in unit time. It should be noted that B is a variable which denotes the link bandwidth of MAC layer. Since MAC layer can support different data rates as a result of protocol standard or in the case of wireless networks, environmental noise, and signal strength, our experimental platform allows rate adaptation according to the quality of the transmission medium. Thus, B can be obtained from hardware and maintained by higher layer protocol to calculate ATT.

IEEE 802.11 uses DCF algorithm to control media access, which is carrier sense multiple access with collision avoidance (CSMA/CA) strategy. DCF computes back-off time by binary exponential strategy as in the following equation:

BackoffTime = Random () \times aslotTime

(5)

aslotTime denotes continuous time of a slot. Random() denotes a pseudorandom number which is uniformly distributed within [0, CW]. CW means contention window. It depends on the count of data transmission errors.

CW

is set to

C W_{\min}

(minimum contention window) at the beginning of the first transmission. For successive transmission failure,

CW

increases its value in binary exponential way until

C W_{\max} = 2^{m} C W_{\min}

. Here, m denotes the maximum retransmission count. The physical layer parameters such as aSlotTime,

C W_{\min}

, and

C W_{\max}

are defined in [12].

CSMA/CA confirms a successful transmission through the ACK frame which is sent by the destination node. The destination node waits a short interval frame space (SIFS) and sends the ACK frame after receiving a packet. Since SIFS is shorter than DIFS, other nodes will not detect that the channel is idle longer than DIFS during transmission of ACK frame. If the source node did not receive ACK during extended interval frame space (EIFS), it will start retransmission according to the back-off rule of (5). At this time, an exception is that a destination node may have successfully received a packet but failed in the transmission of the ACK frame. The source node cannot differentiate in transmission errors between data frame and ACK.

As known, for the IEEE 802.11 protocol, the relationship between packet loss rate and back-off time is not linear. Linear growth of packet loss count will result in binary exponential growth of backoff time. Therefore, the node will have to wait longer for a chance to send frame, which causes link's bandwidth utilization to decline. ETT cannot accurately assess the average packet transmission time since it does not consider exponential back-off strategy in 802.11 MAC layer.

There are four states for DCF, wait, back-off, success, and collision, as shown in Figure 1.

Figure 1

States.

Let $T_{W}$ , $T_{S}$ , $T_{C}$ , and $T_{B}$ mean time spent respectively in the states of wait, success, collision, and back-off.

T_{W} = T_{DATA} + T_{SIFS} + T_{DIFS},

(6)

T_{B} = Random () \times T_{Slot},

(7)

T_{S} = T_{ACK} + T_{W} + T_{B} .

(8)

In (7),

T_{Slot}

denotes time of a slot

T_{C} = T_{ACK} + T_{W} + T_{B} .

(9)

Neighboring nodes exchange messages by the HELLO to monitor link status. Each node of a link broadcasts HELLO message every τ seconds and calculates forward delivery ratio every w seconds. Correspondingly, the node should receive

n = w / τ

HELLO messages within w seconds. If the receiving node gets a HELLO messages in w seconds while sending node receives b HELLO messages, the sending node's forward delivery ratio

d_{f} = a / n

, as well as reverse delivery ratio

d_{r} = b / n

. Therefore, ETX of link is

ETX = n^{2} / (a \times b)

. After removing, the second number of decimal places of ETX directly. Here, α is the integer part of ETX, and β is the first number of decimal places of ETX.

It experiences success and back-off states when node successfully delivers a packet. If packet loss happens during transmission, the node needs to go through states of backoff, conflict, and success. If packets lose n times, the node experiences n conflicts additionally. Each additional packet loss leads to that back-off time increase in an exponential manner, which causes the cost of link bandwidth. So bandwidth availability $r_{B}$ can be calculated by (10) the time ratio of successfully transmitting n packets and ( $α \times n + β$ ) retransmissions in unit time

\begin{matrix} r_{B} & = \frac{\sum_{i = 1}^{n} T_{S}}{\sum_{i = 1}^{α \times n + β} T_{C}} \\ = \frac{n \times T_{S}}{T_{B} (α, β, n) + (α \times n + β) \times T_{W} + T_{ACK} \times n} . \end{matrix}

(10)

Here,

T_{B} (α, β, n)

denotes the count of back-off time spending on (

α \times n + β

) retransmissions

T_{B} (α, β, n) = W_{α} \times T_{Slot} \times β + \sum_{i = 0}^{α - 1} W_{i} \times T_{Slot} \times n .

(11)

Here,

W_{i}

denotes a pseudorandom number which is uniformly distributed within

[0, 2^{i} \times C W_{\min}]

, and

T_{B} (α, β, n)

consists of summation of two parts. The first part denotes the back-off time of α retransmissions. The other part denotes cumulative back-off time of (

0 \dots α - 1

) retransmissions. The expectation of

W_{i}

is (12).

E [W_{i}] = (2^{i - 1} \times C W_{\min}) .

(12)

Take (12) into (11) to simplify it

T_{B} (α, β, n) = E [W_{α}] \times T_{Slot} \times β + \sum_{i = 0}^{α - 1} E [W_{i}] \times T_{Slot} \times n .

(13)

Generally speaking, $T_{Slot}$ , $T_{DATA}$ , $T_{SIFS}$ , $T_{DIFS}$ , $T_{ACK}$ , and $C W_{\min}$ are fixed [12]. Thus, the bandwidth availability only associates with deliver ratio of both sides. Therefore, ATT is a function of forward and reverse deliver ratio, which can be calculated by periodic HELLO messages and link bandwidth B that can be easily derived from hardware against status of wireless environment.

It is known that ATT is based on ETX. So ATT inherits the feature of additive. The cost of a path p can be described as the accumulative value of each link l in the path

ATT (p) = \sum_{l \in p}^{} ATT (l) .

(14)

4. Experiments

4.1. Experimental Settings

We have developed wireless nodes based on PXA270 processor and embedded Linux. Wireless communication is achieved by RT3070 chip which is compatible with 802.11n protocol. The full-function OLSR protocol is implemented on the basis of OLSR daemon written by University UniK. It supports both IPv4 and IPv6 addressing. Differing from other protocol stacks in the Linux kernel, OLSR daemon is implemented at the application layer in order to avoid kernel collapsing because of error programs. ETT and ATT routing metrics are implemented using the plugin of link probe which is developed by Pedro. In our experimental platform, B is obtained from lower layer and maintained by higher layer protocol according to the quality of the transmission medium. Besides, we also bring ETT and ATT link quality algorithm code to olsrd, which corporates with routing metrics and additional ETT and ATT value to LQ HELLO and LQ TC messages. Therefore, latest ETT and ATT will be carried to its neighbors with LQ HELLO messages and spread to all other nodes in the MANET through TC messages periodically, which makes no additional cost to global information collection of routing protocol.

Due to limited actual conditions, the test environmental layout is shown in Figure 2. Wireless nodes work in ad hoc and 802.11n mode using channel 1. The highest point to point bandwidth is 130 Mbps. In order to test the actual throughput, packet loss rate and delay jitter from end to end. Laptop computers A and B, which run Iperf UDP server and client respectively with 250 KB UDP buffer, are placed at the ends of the corridor.

Figure 2

Performance testing.

4.2. Test Results

IEEE 802.11 and Ethernet protocols use the same size of MTU (1500 Bytes). In our experiments, we use different size of UDP packets under 2 M bandwidth to test throughput, packet loss rate, and delay jitter between node A and B. Parameters of OLSR daemon are shown in Table 1, and ATT's parameters are the same with ETX's. The experimental results are shown in Figure 3.

Table 1

OLSR parameters.

Protocol Parameters	Value
HelloInterval	2.0 s
HelloValidityTime	20.0 s
LinkQualityWinSize	12
TcInerval	5.0 s
TcValidityTime	30.0 s
ETX_interval	5 s
ETT_window	6
Emission_interval	5.0 s
ETT_expiration_time	30.0 s

Figure 3

Throughput.

As shown in Figures 4, 5, and 6, along with the change of packet size, ATT does better than ETT and ETX. Actually, the packet of 1000 bytes could take full advantage of channel bandwidth with minimal jitter delay. The throughput is very close to 2 M. Otherwise, large packet (>1500 bytes) has greater impact on the throughput and jitter than small one. It is due to that UDP protocol cannot guarantee the arriving order of packets according to ID because of packet fragmentation and defragmentation. Basically, small packet has better performance than large packet.

Figure 4

Jitter.

Figure 5

Packet loss rate.

Figure 6

Throughput.

The packet of 1000 bytes has the lowest packet loss rate. Based on the above discussion, we know that it has better performance than others under bandwidth of 2 M. Subsequently, we use packet of 1000 bytes to test and compare performance of ETX, ETT, and ATT under different bandwidth conditions.

Figure 6 shows the end-to-end throughput. Benefiting from the high bandwidth of 802.11n, the end-to-end throughput is up to 8 Mbps satisfying the various requirements of transmission bandwidth for different services.

Figures 6 and 7 show that packet loss rate increase along with bandwidth because of radio channel competition and UDP buffer overflow. In Figure 8, when the bandwidth increases, jitter increases. More UDP packets will be cached in the buffer. Packets can not be transmitted timely will result in the increasing of delay jitter. Audio signal is more sensitive to jitter than channel bandwidth. Certain audio application should choose the appropriate bandwidth.

Figure 7

Packet loss rate.

Figure 8

Jitter.

5. Conclusions

This paper takes back-off algorithm of MAC layer, which is ignored in ETX and ETT into account. With the analysis of 802.11 DCF, the route metric of ATT based on bandwidth availability is proposed. The ATT routing metric is extended and implemented using the Linux platform with 802.11n/OLSR protocols. The test results in experiments of ETX, ETT, and ATT show that ATT is more excellent in packet loss rate, jitter, and throughput than other two routing metrics since that ATT considers link condition together with actual transfer rate to get the best performance.

References

Parissidis

Karaliopoulos

Baumann

Guide to wireless mesh networks computer communication and networks

Springer 2009 199 230

Z. P.

Guo

G. S.

Quasi-dynamic channel assignment algorithm for 802.11 wireless mesh networks

Journal of Electronics and Information Technology 2009 31 6 1465 1469

2-s2.0-67649604839

Razak

Kolar

Abu-Ghazaleh

N. B.

A MAC interaction aware routing metric in wireless network

Proceedings of the 13th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM '10)

October 2010

Turkey

118 121

2-s2.0-78650211273

10.1145/1868521.1868541

Yang

Lee

Yun

Han

Yun

Analysis and proposal of wireless mesh network's routing metric for WBAN

Proceedings of the 1st International Conference on Networks and Communications (NetCoM '09)

December 2009

Chennai, India

400 403

2-s2.0-77949843953

10.1109/NetCoM.2009.37

De Couto

D. S. J.

Aguayo

Bicket

Morris

A high-throughput path metric for multi-hop wireless routing

Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom '03)

September 2003

134 146

2-s2.0-1542359009

Draves

Padhye

Zill

Routing in multi-radio, multi-hop wireless mesh networks

Proceedings of the Annual International Conference on Mobile Computing and Networking (MOBICOM '04)

2004

Philadelphia, Pa, USA

ACM Press

114 128

Park

J. C.

Kasera

S. K.

Expected data rate: an accurate high-throughput path metric for multi-hop wireless routing

2005

Proceedings of the 2nd Annual IEEE Communications Society Conference on Sensor and AdHoc Communications and Networks (SECON '05)

2005

Santa Clara, Calif, USA

218 228

10.1109/SAHCN.2005.1557077

Yang

Wang

Kravets

Designing routing metrics for mesh networks

Proceedings of the IEEE Workshop on Wireless Mesh Networks (WiMesh '05)

month year

2005

315 321

Chen

Yang

Zhu

A novel high throughput routing metric for wireless mesh networks

Journal of Chongqing University of Posts and Telecommunications 2008 20 1 58 62

10.

Esposito

P. M.

Campista

M. E. M.

Moraes

I. M.

Costa

L. H. M. K.

Duarte

O. C. M. B.

Rubinstein

M. G.

Implementing the expected transmission time metric for OLSR wireless mesh networks

Proceedings of the 1st IFIP Wireless Days (WD '08)

November 2008

Dubai, UAE

1 5

2-s2.0-67649726052

10.1109/WD.2008.4812900

11.

Kim

Lee

Choi

Lee

S. J.

MAC-aware routing metric for 802.11 wireless mesh networks

Proceedings of the IEEE 20th Personal, Indoor and Mobile Radio Communications Symposium (PIMRC '09)

September 2009

Tokyo, Japan

47 51

2-s2.0-77952849917

10.1109/PIMRC.2009.5450225

12.

IEEE std 802.11-2007 Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications

2007

13.

Clausen

Jaqcquet

Optimized link state routing (OLSR) RFC 3626

IETF Networking Group, 2003

14.

Draves

Padhye

Zill

Routing in multi-radio, multi-hop wireless mesh networks

Proceedings of the 10th Annual International Conference on Mobile Computing and Networking

2004

114 128

An Available Transmission Time Routing Metric for Wireless Ad-Hoc Sensor Networks

Abstract

1. Introduction

2. Routing Metric

2.1. Expected Transmission Count

2.2. Expected Transmission Time

3. ATT Routing Metric

4. Experiments

4.1. Experimental Settings

4.2. Test Results

5. Conclusions

References