Abstract
This paper addresses the path selection problem arising in multi-hop sensor networks, e.g., Smart Grids. A set of multi-hop paths, of varying transmission quality, connect source and destination nodes. The source must select one path for each message to send without knowing the state of the hops. It can however use information deduced from earlier transmissions to decide on a good path for the current message. The goal is to maximize the discounted number of successfully delivered messages. We prove that the myopic routing policy, arguably the most appealing known way to tackle this problem, can permanently ignore good paths. We also generalize an empirically proven good approach, the Whittle index, and show its intractability for the problem at hand. We propose a new tractable metric, Harmonic Discounted Index (HDI), as a measure of attractiveness of transmitting over a path. We evaluate the performance of our HDI metric in a variety of simulation scenarios revealing a superior performance compared to all alternative index policies.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
In practice these probabilities can change and can be well approximated [15].
- 3.
The exact nature of the packet-drop detection mechanism is not of interest in this work, which is only a first step towards a solution of the general problem. Delayed and incorrect packet-drop detection are beyond the scope of this work.
- 4.
- 5.
The subsidy, \(\lambda \), can be thought of as a counter reward for idling the path.
- 6.
The only inefficiency of selecting \(Path_2\) over \(Path_1\) may be the extra transmission energy; however energy is not a focus in this work as devices can be main-powered.
- 7.
We provide in [7] the routing algorithm which runs at the source node.
References
Ahmad, S., Liu, M., Javidi, T., Zhao, Q., Krishnamachari, B.: Optimality of myopic sensing in multichannel opportunistic access. IEEE Trans. Inf. Theor. 55(9), 4040–4050 (2009)
Bertsekas, D.P.: Dynamic Programming and Optimal Control, 2nd edn. Athena Scientific, Belmont (2000)
Bumiller, G., Lampe, L., Hrasnica, H.: Power line communication networks for large-scale control and automation systems. IEEE Commun. Mag. 48(4), 106–113 (2010)
Chatterjee, K., Majumdar, R.: Discounting and averaging in games across time scales. Int. J. Found. Comput. Sci. 23(3), 609–625 (2012)
Johnson, D.M.D., Hu, Y.: The dynamic source routing protocol (DSR) for mobile Ad hoc networks for IPv4. Technical report, IETF (2007). http://tools.ietf.org/html/rfc4728
DLC+VIT4IP. Scenarios and requirements specification. Technical report, 1010. http://www.dlc-vit4ip.org/wb/media/Downloads
Dzung, D., Guerraoui, R., Kozhaya, D., Pignolet, Y.-A.: Dynamic path selection in source routing for time-varying lossy networks. Technical report, Extended version (2014). http://infoscience.epfl.ch/record/206986
Dzung, D., Pignolet, Y.-A.: Dynamic selection of wireless/powerline links using Markov decision processes. In: IEEE SmartGridComm (2013)
Elliott, E.O.: Estimates of error rates for codes on burst-noise channels. Bell Syst. Tech. J 42, 1977–1997 (1963)
Gilbert, E.N., et al.: Capacity of a burst-noise channel. Bell Syst. Tech. J 39(9), 1253–1265 (1960)
Guha, S., Munagala, K., Shi, P.: Approximation algorithms for restless bandit problems. J. ACM 58(1), 1–50 (2010)
Hasslinger, G., Hohlfeld, O.: The gilbert-elliott model for packet loss in real time services on the internet. In: MMB, pp. 1–15, March 2008
Liu, K., Zhao, Q.: Indexability of restless bandit problems and optimality of whittle index for dynamic multichannel access. IEEE Trans. Inf. Theor. 56(10), 5547–5567 (2010)
Mitton, N., Sericola, B., Tixeuil, S., Fleury, E., Lassous, I.G.: Self-stabilization in self-organized wireless multihop networks? Ad Hoc Sens. Wireless Netw. 11(1–2), 1–34 (2011)
Nayyar, N., Gai, Y., Krishnamachari, B.: On a restless multi-armed bandit problem with non-identical arms. In: Allerton, pp. 369–376 (2011)
Ny, J., Dahleh, M., Feron, E.: Multi-uav dynamic routing with partial observations using restless bandit allocation indices. In: American Control Conference, pp. 4220–4225 (2008)
Rao, R., Akella, S., Guley, G.: Power line carrier (PLC) signal analysis of smart meters for outlier detection. In: IEEE SmartGridComm, pp. 291–296 (2011)
Tang, C., McKinley, P.K.: Modeling multicast packet losses in wireless lans. In: MSWIM 2003, pp. 130–133. ACM, New York (2003)
Vasseur, J.: Terminology in low power and lossy networks. Technical report, Cisco Systems Inc. (2013)
Vasseur, J.-P., Dunkels, A.: Interconnecting smart objects with IP: the next internet. Morgan Kaufmann Publishers, Inc. (2010)
Weber, R.R., Weiss, G.: On an index policy for restless bandits. Journal of Applied Probability, pp. 637–648 (1990)
Whittle, P.: Restless bandits: activity allocation in a changing world. J. Appl. Probab. 25, 287–298 (1988)
Winter, T., Thubert, P., Brandt, A., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, J., Alexander, R.: RPL: IPv6 routing protocol for low-power and lossy networks. Technical report, IETF (2012). http://tools.ietf.org/html/rfc6550
Zayen, B., Hayar, A., Noubir, G.: Game theory-based resource management strategy for cognitive radio networks. Multimedia Tools Appl. 70(3), 2063–2083 (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Dzung, D., Guerraoui, R., Kozhaya, D., Pignolet, YA. (2015). Source Routing in Time-Varing Lossy Networks. In: Bouajjani, A., Fauconnier, H. (eds) Networked Systems . NETYS 2015. Lecture Notes in Computer Science(), vol 9466. Springer, Cham. https://doi.org/10.1007/978-3-319-26850-7_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-26850-7_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26849-1
Online ISBN: 978-3-319-26850-7
eBook Packages: Computer ScienceComputer Science (R0)