پخش حداقل انرژی در شبکه‌های حسگر بی‌سیم: راهکار بهینه سازی کلونی مورچگان برای یک مدل آنتن واقع گرایانه

The classical minimum energy broadcast (MEB) problem in wireless adhoc networks, which is well-studied in the scientific literature, considers an antenna model that allows the adjustment of the transmission power to any desired real value from zero up to the maximum transmission power. However, when specifically considering sensor networks, a look at the currently available hardware shows that this antenna model is not very realistic. A first contribution of this work is therefore the re-formulation of the MEB problem for an antenna model that is realistic for sensor networks. In this antenna model transmission power levels are chosen from a finite set of possible ones. The second contribution concerns the adaptation of ant colony optimization, a current state-of-the-art algorithm for the classical MEB problem, to the more realistic problem version. The obtained results show that the advantage of ant colony optimization over classical heuristics even grows when the number of possible transmission power levels decreases.

Sensor networks are wireless adhoc networks that are being used in practical scenarios such as the monitoring of certain events [1]. Sensor nodes are generally equipped with omni-directional antennas for sending and receiving information. They have a packet-forwarding capability in order to communicate via shared and limited radio channels. In order to transmit information, a sender node must adjust its transmission power in order to reach the desired receiver node. As network lifetime is limited by batteries, energy saving is critical. A fundamental problem in sensor networks arises when one node is required to transmit data to all other nodes of the network. This scenario is known as broadcasting. Obviously, for broadcasting to be energy-efficient, the transmission powers of the sensor nodes should be adjusted such that the sum of the energy spent by all nodes is minimized. This problem is know as the minimum energy broadcast (MEB) problem in the literature [2]. To our knowledge, all existing works from the literature use an antenna model which allows the adjustment of the transmission powers to any real value between zero and the maximum transmission power. However, available hardware such as SunSPOTs (see http://www.sunspotworld.com/) or iSense sensor nodes (see http://www.coalesenses.com/) are equipped with antennas that offer a limited set of different transmission power levels; 201 in the case of SunSPOTs and seven in the case of the iSense hardware. Note that SunSPOTs are among the most widely used sensor hardware, while iSense nodes are used by two of the currently largest European projects on sensor networks, FRONTS and WISEBED.1

In this work we have first introduced a generalization of the classical minimum energy broadcast problem in wireless adhoc networks such as sensor networks. The introduced generalization concerns the fact that in many radio antennas used in real sensor network hardware, the choice of a transmission power level is limited to a discrete set of values, rather than being unlimited. As a second contribution we adapted ant colony optimization, a current state-of-the-art algorithm for the classical minimum energy broadcast problem, to the problem generalization. The experimental results have shown that the advantage of this algorithm over classical heuristics even grows when the number of available transmission power levels decreases. In the future we plan to develop a distributed version of the ant colony optimization algorithm for minimum energy broadcasting. Note that the use of a distributed algorithm is always necessary when the structure of the deployed network is unknown, which might be the case in quite a few applications of sensor networks. In this context, the development of suitable heuristic information for solution construction as well as the development of distributed solution improvement procedures will be the main challenges.