Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-24T17:58:52.654Z Has data issue: false hasContentIssue false
  • English
  • Français

Sensor allocation problems on the real line

Part of: Markov processes Computer system organization

Published online by Cambridge University Press:  24 October 2016

Evangelos Kranakis  and
Gennady Shaikhet
Evangelos Kranakis*
Affiliation:
Carleton University
Gennady Shaikhet*
Affiliation:
Carleton University
*
*Postal address: School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, ON, K1S 5B6, Canada. Email address: [email protected]
** Postal address: School of Mathematics and Statistics, Carleton University, 1125 Colonel By Drive, Ottawa, ON, H1S 5B6, Canada. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A large number n of sensors (finite connected intervals) are placed randomly on the real line so that the distances between the consecutive midpoints are independent random variables with expectation inversely proportional to n. In this work we address two fundamental sensor allocation problems. The interference problem tries to reallocate the sensors from their initial positions to eliminate overlaps. The coverage problem, on the other hand, allows overlaps, but tries to eliminate uncovered spaces between the originally placed sensors. Both problems seek to minimize the total sensor movement while reaching their respective goals. Using tools from queueing theory, Skorokhod reflections, and weak convergence, we investigate asymptotic behaviour of optimal costs as n increases to ∞. The introduced methodology is then used to address a more complicated, modified coverage problem, in which the overlaps between any two sensors can not exceed a certain parameter.

Keywords

Sensor allocationqueueing theorypotential outflowreflected random walkSkorokhod mapweak convergence

MSC classification

Primary: 60J20: Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
Secondary: 68M20: Performance evaluation; queueing; scheduling
Type
Research Papers
Information
Journal of Applied Probability , Volume 53 , Issue 3 , September 2016 , pp. 667 - 687
Copyright
Copyright © Applied Probability Trust 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Atar, R.,Mandelbaum, A. and Reiman, M. I. (2004).Scheduling a multiclass queue with many exponential servers: asymptotic optimality in heavy traffic..Ann. Appl. Prob. 14,1084–1134.Google Scholar
[2] Burkhart, M.,von Rickenbach, P.,Wattenhofer, R. and Zollinger, A.. (2004).Does topology control reduce interference?. In Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing,ACM,New York, pp.9–19.Google Scholar
[3] Chen, H. and Yao, D., (YEAR).Fundamentals of Queueing Networks,Springer,New York.Google Scholar
[4] Czyzowicz, J. et al. (2009).On minimizing the maximum sensor movement for barrier coverage of a line segment. In Ad-Hoc, Mobile and Wireless Networks,Springer,Berlin, pp.194–212.CrossRefGoogle Scholar
[5] Czyzowicz, J. et al. (2010).On minimizing the sum of sensor movements for barrier coverage of a line segment. In Ad-Hoc, Mobile and Wireless Networks,Springer,Berlin, pp.29–42.Google Scholar
[6] Huang, C.-F. Tseng, Y.-C. (2005).The coverage problem in a wireless sensor network.Mobile Networks Appl. 10,519–528.Google Scholar
[7] Jacod, J. and Shiryaev, A. N. (2003).Limit Theorems for Stochastic Processes, 2nd edn.Springer,Berlin.CrossRefGoogle Scholar
[8] Karatzas, I. and Shreve, S. E.(1991).Brownian Motion and Stochastic Calculus,Springer,New York.Google Scholar
[9] Kranakis, E. and Shaikhet, G.(2014).Displacing random sensors to avoid interference. In Computing and Combinatorics,Springer,Heidelberg, pp.501–512.Google Scholar
[10] Kranakis, E. et al. (2013).Expected sum and maximum of displacement of random sensors for coverage of a domain. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures,ACM,New York, pp.73–82.Google Scholar
[11] Kumar, S.,Lai, T. H. and Arora, A.. (2005).Barrier coverage with wireless sensors. In Proceedings of the 11th Annual International Conference on Mobile Computing and Networking,ACM,New York, pp.284–298.Google Scholar
[12] Kuo, H.-H. (2006).Introduction to Stochastic Integration,Springer,New York.Google Scholar
[13] Meyn, S. and Tweedie, R. L.(2009).Markov Chains and Stochastic Stability, 2nd edn.Cambridge University Press.CrossRefGoogle Scholar
[14] Moscibroda, T. and Wattenhofer, R.(2005).Minimizing interference in ad hoc and sensor networks. In Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing,ACM,New York, pp.24–33.Google Scholar
[15] Prabhu, N. U. (1998).Stochastic Storage Processes: Queues, Insurance Risk, Dams, and Data Communication (Appl. Math. (New York) 15), 2nd edn,Springer,New York.Google Scholar
[16] Serfozo, R. (2009).Basics of Applied Stochastic Processes,Springer,Berlin.CrossRefGoogle Scholar