Small-world effects in wireless agent sensor networks

Coverage, fault tolerance and power consumption constraints make optimal placement of mobile sensors or other mobile agents a hard problem. We have developed a model for describing and analysing the coverage graph that results from the particular physical placement of mobile agents or sensor devices. The planar graph for the devices can usefully be augmented by small-world network “shortcuts”; the resulting network then has properties intermediate between those of a fixed regular mesh and a random graph. Various results from computational physics involving percolation and scaling phenomena can be used to interpret the behaviour of such networks. Individual mobile sensors can be modelled as points in Euclidean space with a simple circular region of influence and awareness; clustering algorithms can be used to construct connectivity graphs which can be then analysed using conventional graph methods. We describe some small-world e↵ects that arise from particular geometric networking arrangements and which can be exploited to improve coverage, fault tolerance and the lifetime of the sensor network.