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

Research Article

Random Walks on Sensor Networks

  • @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 Lima1,*, Joao Barros1,*
  • 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).