Random Walks on Sensor Networks

Luisa Lima; Joao Barros

5th International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks

Research Article

Random Walks on Sensor Networks

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1109/WIOPT.2007.4480064,
    author={Luisa Lima and Joao Barros},
    title={Random Walks on Sensor Networks},
    proceedings={5th International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks},
    publisher={IEEE},
    proceedings_a={WIOPT},
    year={2008},
    month={3},
    keywords={Computer science  Large-scale systems  Mobile computing  Mobile robots  Navigation  Radio access networks  Robot sensing systems  Sensor phenomena and characterization  Telecommunications  Wireless sensor networks},
    doi={10.1109/WIOPT.2007.4480064}
}

Luisa Lima
Joao Barros
Year: 2008
Random Walks on Sensor Networks
WIOPT
IEEE
DOI: 10.1109/WIOPT.2007.4480064

Luisa Lima¹^,*, Joao Barros¹^,*

1: Instituto de Telecomunicagoes Department of Computer Science Universidade do Porto, Portugal

*Contact email: luisalima@dcc.fc.up_pt, barros@dcc.fc.up.pt

Abstract

We consider the mobile data gathering problem in large-scale wireless sensor networks with static sensor nodes and a mobile patrol node. Based on the assumptions that (a) the sensor positions are unknown and (b) the network may not be entirely connected, we formulate the problem as one of random walks in random geometric graphs and derive analytical bounds for the node coverage, i.e. the number of queried sensor nodes within a given time frame. Based on this metric, we propose an algorithm that improves the data gathering performance by generating constrained random walks, in which the probability mass function at each step reflects the available side information (e.g. the memory of past visited sites).

Keywords: Computer science Large-scale systems Mobile computing Mobile robots Navigation Radio access networks Robot sensing systems Sensor phenomena and characterization Telecommunications Wireless sensor networks

Published: 2008-03-31
Publisher: IEEE
Modified: 2011-07-28

: http://dx.doi.org/10.1109/WIOPT.2007.4480064