Multipath Routing for Dual-Radio Wireless Sensor Networks
Resumo
The design of a Wireless Sensor Network depends significantly on the application. For the traditional applications, such as environmental monitoring, smart buildings or agriculture, the design prioritized reducing the cost, the energy expenditure and memory usage at the expense of not having a higher throughput. Modern applications, such as surveillance or traffic monitoring, usually require using cameras and transmitting video data through the network. For such applications, dual-radio platforms were developed where their design prioritizes achieving higher throughput and conserve the energy efficiency of In this work, we propose a multipath routing algorithm to find the network. two disjoint paths with the same parity between a pair of nodes in the network. The new routing algorithm, combined with a forwarding scheme that alternates the radios throughout the paths, allows all nodes in the paths to use both radios in parallel all the time, doubling the throughput in comparison with a single path routing scheme. We evaluated our algorithm and forwarding scheme in a real world testbed with 100 nodes of the Opal dual-radio platform. Our scheme were able to double the throughput when compared with FastForward, the state-of-the-art protocol for dual-radio platforms, and achieve up to 96% of the theoretical limit.
Referências
Bhandari, R. (1997). Optimal physical diversity algorithms and survivable networks. In Computers and Communications, 1997. Proceedings., Second IEEE Symposium on, pages 433–441. IEEE.
Chen, Y.-q., Guo, X.-f., Zeng, Q.-k., and CHEN, G.-h. (2004). Amr: a multipath routing algorithm based on maximum ow in ad-hoc networks. Acta Electronica Sinica, 32(8):1297–1301.
Ekbatanifard, G., Sommer, P., Kusy, B., Iyer, V., and Langendoen, K. (2013). Fastforward: High-throughput dual-radio streaming. In Mobile Ad-Hoc and Sensor Systems (MASS), 2013 IEEE 10th International Conference on, pages 209–213. IEEE.
Fang, X., Shi, S., and Li, J. (2009). A disjoint multi-path routing algorithm in wireless sensor network. Journal of Computer Research and Development, 46(12):2053–2061.
Ganesan, D., Govindan, R., Shenker, S., and Estrin, D. (2001). Highly-resilient, energyefcient multipath routing in wireless sensor networks. ACM SIGMOBILE Mobile Computing and Communications Review, 5(4):11–25.
Grifn, M. and Korkmaz, T. (2011). Distributed verication of global multiple disjoint paths in mobile wireless networks. In Wireless Communications and Mobile Computing Conference (IWCMC), 2011 7th International, pages 666–670. IEEE.
Hashiguchi, T., Tajima, K., Takita, Y., and Naito, T. (2011). Node-disjoint paths search in wdm networks with asymmetric nodes. In Optical Network Design and Modeling (ONDM), 2011 15th International Conference on, pages 1–6. IEEE.
Ishida, K., Kakuda, Y., and Kikuno, T. (1995). A routing protocol for nding two nodedisjoint paths in computer networks. In Network Protocols, 1995. Proceedings., 1995 International Conference on, pages 340–347. IEEE.
Iwama, K., Iwamoto, C., and Ohsawaa, T. (1997). A faster parallel algorithm for kconnectivity. Information processing letters, 61(5):265–269.
Jurdak, R., Klues, K., Kusy, B., Richter, C., Langendoen, K., and Brünig, M. (2011). Opal: A multiradio platform for high throughput wireless sensor networks. Embedded Systems Letters, IEEE, 3(4):121–124.
Khuller, S. and Schieber, B. (1991). Efcient parallel algorithms for testing k and nding disjoint s-t paths in graphs. SIAM Journal on Computing, 20(2):352–375.
Kumar, A. and Varma, S. (2010). Geographic node-disjoint path routing for wireless sensor networks. IEEE Sensors Journal, 10(6):1138–1139.
Kusy, B., Richter, C., Hu, W., Afanasyev, M., Jurdak, R., Brünig, M., Abbott, D., Huynh, C., and Ostry, D. (2011). Radio diversity for reliable communication in wsns. In Information Processing in Sensor Networks (IPSN), 2011 10th International Conference on, pages 270–281. IEEE.
LaPaugh, A. S. and Papadimitriou, C. H. (1984). The even-path problem for graphs and digraphs. Networks, 14(4):507–513.
Lee, Y. O. and Reddy, A. N. (2010). Disjoint multi-path routing and failure recovery. In Communications (ICC), 2010 IEEE International Conference on, pages 1–6. IEEE.
Li, Q., Han, D., Gnawali, O., Sommer, P., and Kusy, B. (2013). Twonet: Large-scale In Proceedings of the 11th wireless sensor network testbed with dual-radio nodes. ACM Conference on Embedded Networked Sensor Systems, page 89. ACM.
Li, S. and Wu, Z. (2005). Node-disjoint parallel multi-path routing in wireless sensor networks. In Embedded Software and Systems, 2005. Second International Conference on, pages 6–pp. IEEE.
Ogier, R. and Shacham, N. (1989). A distributed algorithm for nding shortest pairs of disjoint paths. In INFOCOM'89. Proceedings of the Eighth Annual Joint Conference of the IEEE Computer and Communications Societies. Technology: Emerging or Converging, IEEE, pages 173–182. IEEE.
Omar, S., Zoulikha, M., and Cousin, B. (2011). Energy efciency in ad hoc wireless In Systems, Signal Processing and their networks with node-disjoint path routing. Applications (WOSSPA), 2011 7th International Workshop on, pages 127–130. IEEE.
Sidhu, D., Nair, R., and Abdallah, S. (1991). Finding disjoint paths in networks. In ACM SIGCOMM Computer Communication Review, volume 21, pages 43–51. ACM.
Srinivas, A. and Modiano, E. (2003). Minimum energy disjoint path routing in wireless ad-hoc networks. In Proceedings of the 9th annual international conference on Mobile computing and networking, pages 122–133. ACM.
Suurballe, J. (1974). Disjoint paths in a network. Networks, 4(2):125–145.
Zhang, K., Han, Q., Yin, G., and Pan, H. (2016). Ofdp: a distributed algorithm for nding disjoint paths with minimum total length in wireless sensor networks. Journal of Combinatorial Optimization, 31(4):1623–1641.
