Recently, small electronic devices were developed with the idea of monitor hostile areas. These devices are provided with several sensors to measure diverse environmental parameters, e.g., temperature, humidity, pressure, soil makeup, noise levels, etc. Due to its nature, these devices are called sensors. And also, the sensors has processing capabilities. Furthermore, they are provided with a radio communication system, using a single shared channel to transmit and receive radio signals. Usually, the capacity of this radio system is small, i.e., the radii of transmission and reception are small with respect to the size of the monitored area. The sensors are designed to be easily and massively deployed in unreachable areas, usually it is assumed that they will be deployed from the air using, for instance, an airplane. Hence, they are tiny enough so that several of them fit in one hand.
The goal is, once the sensors are deployed they start an infitnite communication process among them in order to build a Sensor Network. This communication process is carried out using radio communication, but due to the single shared (transmission or reception) channel, sensors must deal with collisions of transmissions, and when a sensor is transmitting it can not receive any other transmission. Hence, a really special situation is necessary to effectively establish the communication, a node receive a transmission when only one of its possible transmitters (sensors into its reception radius) is transmitting and the rest are in silence. Due to the random nature of the sensors deployment, it is impossible to predetermine anything about the sensors that will be in the transmission (or reception) radius of another sensor. Hence, it is very challenging to determine communication patterns for the sensors, in order to maintain the network, and the communication, during an infinite period of time.
Most of the communication patterns, or protocols, for sensors in sensor networks use randomness to deal with collisions and the lack of information about the network. Randomized protocols are usually fast and resilient to failures, but they frequently rely on redundant transmissions. Given that the most restrictive resource in sensor networks is energy and that the dominating factor in energy consumption is the radio communication, deterministic solutions may yield energy-efficient solutions.
The model.
Sensors are represented by n nodes deployed randomly in R^2, and the Sensor Network by a Geometric Graph using these n nodes, where an undirected edge connect a pair of nodes if and only if they are at an Euclidean distance of at most a parameter r. Given the random deployment of the nodes, we assume that the topology of the network is unknown. Nevertheless, it is assumed that the network is connected and that the maximum degree of any node is bounded by a parameter k < n. Time is assumed to be slotted. In a time slot a node can be transmitting or receiving. The communication among neighboring nodes is through broadcast, i.e., a node transmit to all its neighbors, defined by the graph, at the same time. Finally, nodes are activated adversarially, i.e., nodes are deployed in a sleeping mode, and an adversary decides the activation moment.
Definition 1. If in a given slot exactly one of the adjacent neighbors of a node x transmits, and x it self is not transmitting, we say that there was a clear reception at x in that time slot.
Definition 2. If the node x transmits a message in a given time slot, and no other node within two hops of x transmits in the same time slot, we say that there was a clear transmission for node x.
And now the problem in a Sensor Network.
Problem 1. Given a Sensor Network of n nodes and maximum degree k, where nodes are activated possibly at different times, and upon activation stay active forever, in order to solve the Recurring Reception problem every active node must clearly receive from all of its active neighboring nodes infinitely many times.
Problem 2. Given a Sensor Network of n nodes and maximum degree k, where nodes are activated possibly at different times, and upon activation stay active forever, in order to solve the Recurring Transmission problem every active node must clearly transmit to all of its active neighboring nodes infinitely many times.
Since the post is too long until now, I will let you some weeks to think in possible solutions, or in some equivalent problem previously stated in a different context, maybe combinatorics.
No hay comentarios:
Publicar un comentario