Link Estimation Metrics
Link Estimation is an integral part of reliable communication in wireless networks. Various link estimation metrics have been proposed to effectively measure the quality of wireless links, however, the performance of those metrics has never been studied extensively. In this research project, I compared the performance three common link estimation metrics and analyzed the reasons behind the performance observed. By studying the current link metrics, I hope to gain insights on a bigger question: how can we improve current metric to provide better link estimation?Project Description
This research focus on conducting a detailed performance analysis of three commonly used link-quality metrics in wireless sensor networks: ETX, 4Bit, and RNP. We study the interplay between these metrics and CTP, a tree-based routing protocol provided by TinyOS. The goal of the project is to provide extensive evaluation of ETX, 4Bit and RNP with insights on their performance under different criteria.
Motivation
Due to the dynamic and asymmetric nature of the wireless links, various link quality estimation metrics have been proposed in literature to cope with the vagaries of the communication channel. In previous research, link reliability estimation metrics such as ETX and RNP have been proved to perform superior as compared to conventional metrics like shortest path or minimum latency in wireless sensor networks.
The question being asked In this research project is simple: which metric can deliver the best performance? To answer this question, we extensively evaluated some of the most commonly used link estimation techniques based on link reliability and compared the performance of these metrics with different but realistic network conditions.
In Additional, blacklisting policy is used in default link estimator of TinyOS as a part of multihop routing stack, but the actual effects of blacklisting in realistic network configurations have not been extensively studied. To answer this question, we studied the the impact of the presence or absence of a blacklisting policy when using these link quality estimation metrics.
Experiments
Testbed: We conducted our experiments using a testbed located on one floor of a office building, with the nodes placed along the ceiling of a long corridor. There are 33 nodes in total, organized into 11 groups of 3 motes. Each group of motes are mounted on a bar with one foot separation. The location of these 11 bars are depicted in Figure 1.
 |
Figure 1: Placement of
Nodes |
Experiment Settings: We experimented with four different network configurations: 11 nodes with 0dBm and -10dBm transmission power; 33 nodes with 0dBm and -10dBm transmission power. To increase the diameter of the network, the root node was set at one end of the corridor. In 11-node experiments, the nodes are evenly separated within 250 feet distance. In 33-node experiments, the nodes are divided into 11 groups, each group contains 3 nodes.
Results
Both ETX and 4Bit use the ETX metric for link estimation. 4B combines information from physical and network layer to provide more efficient link estimation to the upper layer. The other metric, RNP accounts for the distribution of packet losses of a link when estimating link quality. it represents the number of transmissions attempts including retransmissions to deliver a packet whereas ETX represents the number of transmissions required to deliver a packet without retransmission.
In our results, ETX and 4Bit exhibit the same preference in choosing paths with near perfect links. As a result, the average path length for ETX and 4B is almost the same. Since ETX selects parent nodes based solely on the quality of its neighbors, it has much better path quality and is more adaptive to changes in link quality.
By definition, RNP gives higher estimation to links with consecutive losses comparing to delivery rate based ETX. From the routing perspective, RNP tends to use links with less perfect quality that span long distance, therefore often selects paths with less hops to constitute an end-to-end route. Although packet losses occurs more often in longer links, the retransmission mechanism in the routing protocol can still ensure a high delivery rate with a few retransmissions. This is reflected in our experiments at low network densities where RNP chooses paths with less hops than the other two metrics. This leads to a smaller cost for delivering a packet, while maintaining a high end to end delivery rate that is comparable to that of ETX and 4Bit.
We also compared the effect of the presence and absence of blacklisting policy on the routing performance of ETX, RNP and 4Bit. ETX and RNP exhibit better performance without blacklisting with better path quality, higher delivery rates and less overhead. On the other hand, 4B performs much worse without blacklisting, especially in high network density configuration. This counter- intuitive result can be explained by the design of the link estimator: Regardless of the metric, the link estimator maintains records for its 10 best neighbors by link quality. In case of 4B, with blacklisting absent, the link estimator will consult the routing protocol when a new neighbor is discovered. If this neighbor is located closer to the sink, the routing protocol will instruct the link estimator to include this node in the neighbor table. As the link quality to this node could be lower than the node evicted from the neighbor table, the neighbor table will be polluted by such entries. In high power- high network density networks, the number of such nodes will be big enough to affect the routing choices made in 4Bit, resulting in poor delivery rate.
Publications
- Liu12a
- , "TALENT: Temporal Adaptive Link Estimator with No Training," Proceedings of the Tenth ACM conference on Embedded Network Sensor Systems (SenSys 2012), pp. 253--266, Toronto, Ontario, Canada, November, 2012.
- Liu11a
- , "Foresee (4C): Wireless link prediction using link features," Proceedings of the Tenth ACM/IEEE International Conference on Information Processing on Sensor Networks (IPSN 2011), pp. 294--305, Chicago, IL, USA, April, 2011.
- Liu09a
- , "Performance Evaluation of Link Quality Estimation Metrics for Static Multihop Wireless Sensor Networks," Proceedings of the Sixth Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON 2009), pp. 583--591, IEEE, Rome, Province of Rome, Italy, June, 2009.
- Jafari05a
- , "On Minimal Energy Skew Routing in Lossy Wireless Sensor Networks," UCLA Technical Report TR-05-0056, pp. 1--15, Computer Science Department, University of California, Los Angeles, December, 2005.
- Cerpa05b
- , "Temporal Properties of Low Power Wireless Links: Modeling and Implications on Multi-Hop Routing," Proceedings of the Sixth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2005), pp. 414--425, ACM, Urbana-Champaign, Illinois, USA, August, 2005.
- Cerpa05a
- , "Statistical Model of Lossy Links in Wireless Sensor Networks," Proceedings of the Fourth ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN 2005), pp. 81--88, ACM/IEEE, Los Angeles, CA, USA, July, 2005.
- Ganesan04a
- , "Networking Issues in Sensor Networks," Journal of Parallel and Distributed Computing (JPDC), 64 (7), pp. 799--814, Elseiver, 2004.
- Cerpa03a
- , "SCALE: A Tool for Simple Connectivity Assessment in Lossy Environments," CENS Technical Report 0021, pp. 1--13, Center of Embedded Networked Systems (CENS), University of California, Los Angeles, September, 2003.
People
- Naim Busek
- Alberto E. Cerpa
- Deborah Estrin
- Deepak Ganesan
- Soheil Ghiasi
- Roozbeh Jafari
- Lun Jiang
- Ankur Kamthe
- Tao Liu
- Miodrag Potkonjak
- Majid Sarrafzadeh
- Jennifer L. Wong
- Wei Ye
- Yan Yu
- Jerry Zhao
Sponsors
