Grid emulation for managing random sensor networks☆,☆☆
Introduction
A sensor network is usually modelled as a radio network where sensors are spread out at random over a given area according to a uniform distribution. The structure of sensor networks is complex and presents many challenges. This is due to its random characteristic and its induced physical limitations (i.e., energy consumption, transmission range and open medium access constraints).
In a random sensor network usually each sensor does not have any knowledge about the network in which it is working, unless some local information is obtained by exchanging control messages with its neighbors. Moreover, since sensors are placed at random, a first glance might suggest a total lack of structure. This is not necessarily the case. Dealing with randomness is always a problem. One way of dealing with it is by simulations. This solution is time and effort consuming and its accuracy is usually hard to evaluate. Another way of approaching this problem is by applying sophisticated stochastic geometry tools. This approach is again time costly and it is not always simple. Understanding the structure of random sensor networks is a quintessential problem in the field of sensor networks. Clearly an understanding of this structure can lead to a major improvement in energy consumption and in the overall performance of a random network.
A standard and elegant technique when dealing with complex structures is to find a simpler structure that is close enough to the complex one, and yet simple enough to understand (see for instance [8]). This is our main goal in this work.
Our contribution is a grid protocol emulation for random sensor networks. In order to achieve this, we develop optimal scheduling schemes that avoid collisions. More precisely, we propose a general framework that is capable of emulating any protocol based on a grid structure for random sensors. In this way, we break the problem into two steps. The first step is to solve the problem on the grid. Since the grid is a well known and well researched structure, a textbook solution there probably already exists. The second step is to emulate the solution on the random sensor network using our grid emulation protocol. The advantages of this approach are evident. First, there are many problems that are already optimally solved on grids. Second, usually it is much easier to solve a problem on grids than on a random set of points. Moreover, we are going to show that the cost of the grid emulation in terms of consumed energy and time is not too high. In particular, we use our method to solve Broadcast, Gossiping and Leafy Tree problems on random sensor networks, obtaining satisfactory solutions. Last, the grid emulation can also be used as a rule of thumb to evaluate the correctness of simulations.
In order to achieve the grid emulation, we develop a collision-free scheduling scheme. Using this scheduling scheme, we develop a collision-free routing algorithm that can be easily applied in order to perform any desired communication on any sensed area of interest. Our scheme is completely independent of the routing protocol among the location-aware ones [1], [11]. It is worth noting that the combination of the routing protocol with the scheduling scheme is the main key for the conservation of energy in any communication. While the routing scheme, in fact, minimizes the energy needed to perform a desired communication, the scheduling prevents cases where communications must be repeated several times before succeeding due to collisions. This concept was initiated by Friedman and Korland [7] where the authors dealt with random and deterministic scheduling functions. The main differences reside in their main assumptions for which each sensor is aware about the position of any other one and moreover each virtual grid square is assumed to be not empty. They also assume three basic states for the sensors. Active, when a sensor can transmit, Passive, when a sensor can receive and Sleep when a sensor is switched off in order to save energy. Concerning collisions, those are caused by superpositions of the transmission ranges of the sensors as in [3] but in [7] also by an extra range, called interference range (Rp). For the sake of clarity we do not cope with such an extra range but everything is easily scalable.
The paper is organized as follows. In the next section, we describe the model and motivations that led to the assumptions made in the paper. In Section 3, we take care of the MAC-layer in order to avoid colliding communications. We also provide analysis in order to estimate the needed time for a source–destination communication. In Section 4, we show how the combination of a routing protocol with our scheduling scheme can be applied in order to emulate grid structures hence implying a virtual infrastructure on the network (see for instance [15]). Finally, in Section 5 we discuss some conclusive remarks.
Section snippets
Model
As assumed in the large majority of the papers we consider random instances of sensor networks in the two dimensional space (see [1], [11] for a survey on sensor networks routing protocols). The randomness of the spread sensors is usually motivated by applications. The area of interest, in fact, where the sensing must be computed, can be an impervious, even dangerous area so that sensors cannot be suitably set up. Without loss of generality we consider a square area using a uniform
MAC-layer
In this section, we describe a deterministic MAC-layer schedule based on the locations of the transmitters. For simplicity we assume that the sensors lie on a regular 2-dimensional grid G of N = n × n vertices V. We will remove this assumption in Section 4. For the sake of generality, we assume that some of the grid points are free from sensors and that some of them have more than one. The second case can be simplified just by considering one sensor in such grid points, since sensors in the same
Grid emulation
In this section, we apply previous results in order to achieve a general technique for emulating any grid protocol on random sensors. The idea is to “move” points to a grid structure. Movements (Long or Short) are performed by increasing the radius of transmissions to ensure that all the neighbors of the grid structure can communicate. The difference between Long and Short movements concerns the size of the grid structure and the technique to calculate reciprocal locations of the points. More
Conclusion
In this paper, we have shown that the combination of routing and the MAC-layer can be efficient in a sensor network in terms of energy consumption and delivery time. We have proposed a scheduling scheme that perfectly matches with any location-aware routing protocol, hence obtaining a fully functional protocol for sensor networks. We have shown that a simple algorithm can avoid any collision when sensors know their own location and when they are synchronized. Actually we have proposed a
Zvi Lotker received his Ph.D. in 2005 from Tel-Aviv university. He is now a lecturer in the Department of Communication Systems Engineering at Ben-Gurion University. His main work is in communication networks, Computer networks, Distributed systems, Mobile and wireless computing.
References (20)
- et al.
A lower bound for radio broadcast
Journal on Computer and System Sciences
(1991) - et al.
Routing techniques in wireless sensor networks: a survey
IEEE Wireless Communications
(2004) - et al.
Robust position-based routing in wireless ad hoc networks with unstable transmission ranges
- et al.
GPS-less low-cost outdoor localization for very small devices
IEEE Personal Communications
(2000) - A.M. Farley, S.T. Hedetniem, Broadcasting in grid graphs, in: Proceedings of the 9th S-E Conference Combinatorics,...
- et al.
Gossiping in grid graphs
Journal of Combinatorics, Information and System Science
(1980) - R. Friedman, G. Korland, Timed grid routing (tigr) bites off energy, in: Proceedings of the 16th ACM International...
- et al.
From balls and bins to points and vertices
- et al.
Approximation algorithms for minimum time broadcast
- D. R. Kowalski, A. Pelc, Deterministic broadcasting time in radio networks of unknown topology, in: Proceedings of the...
Cited by (2)
Unit disk graph and physical interference model: Putting pieces together
2009, IPDPS 2009 - Proceedings of the 2009 IEEE International Parallel and Distributed Processing Symposium
Zvi Lotker received his Ph.D. in 2005 from Tel-Aviv university. He is now a lecturer in the Department of Communication Systems Engineering at Ben-Gurion University. His main work is in communication networks, Computer networks, Distributed systems, Mobile and wireless computing.
Alfredo Navarra received the degree in Computer Science at the University of L’Aquila in 2000 and the Ph.D. degree in Computer Science at the University of Rome “La Sapienza” in 2004. From 2003 to 2004, he joint the MASCOTTE project team at the INRIA institute of Sophia Antipolis as Ph.D. student and PostDoc for almost two years. In 2005, he was a temporary researcher at the University of L’Aquila. In 2006, he joint the laboratory LaBRI in Bordeaux as PostDoc for one year. In 2007, he has become Assistant Professor at the University of Perugia, Italy. His research interests include algorithms and computational complexity, communication, modelling as well as analysis and experimentation problems on protocols and routing algorithms for interconnection networks such as Ad Hoc, Wireless, Mobile and Sensor Networks. He has authored and co-authored more than 35 papers in his fields of interest published in reputed international conferences and journals.
- ☆☆
The research was partially funded by the European projects COST Action 293, “Graphs and Algorithms in Communication Networks” (GRAAL) and COST Action 295, “Dynamic Communication Networks” (DYNAMO).