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

One of the important tasks in wireless sensor networks is broadcasting, which arises when a sender node has to communicate information to all the other nodes of the network. In order to save energy, which is often a limited resource, broadcasting has to be done efficiently from an energy perspective. Energy efficiency can hereby be achieved by adjusting the transmission power levels of the sensor nodes’ antennas. This classical problem is known as the minimum energy broadcast (MEB) problem. In this work we deal with a generalization of this problem which is known as the minimum energy broadcast problem in sensor networks with realistic antennas (MEBRA). The difference to the classical MEB problem is to be found in a more realistic antenna model. In this work we propose a distributed ant colony optimization algorithm for solving the MEBRA problem. The experimental evaluation of the proposed algorithm shows that it generally improves over the centralized version of a classical heuristic. Moreover, depending on the exact antenna model used, the results of the distributed ant colony optimization algorithm are very close to the results of the centralized algorithm version.

In the 1980s a computer easily filled a whole room and communication between computers was possible by wired links. In the last 20 years many technological advances have pushed the development of new methodologies for networking. Nowadays, not only computers are able to communicate, but also small devices such as mobile phones may be linked by wireless communication networks. The introduction of wireless technology has caused wireless networks to be created on the fly (wireless ad hoc networks). As a result, networks form spontaneously as soon as devices are within the communication range of each other. The above mentioned technological advances have also resulted in the development of a new type of wireless networks, called sensor networks [1]. Sensor nodes are rather small devices whose size ranges from approximately one to seven inches including the wireless radio. Sensor nodes owe their name due to the fact that they are equipped with various sensors which allow them to monitorize physical data such as humidity, light or acceleration. During recent years quite a few applications for sensor networks have been proposed. Examples include environmental monitoring, patient monitoring in health care, etc. Researchers are specially attracted by the ease of use and the numerous features of these networks, which come at a relatively low cost. From an algorithmic perspective, sensor networks are also a useful testbed for distributed algorithms. Their working is based on the exchange of local information between nodes in order to achieve a global goal. Cooperation between the sensor nodes is an important feature for the compensation of their shortcomings when solving complex tasks. Ad hoc and sensor networks are sometimes implemented in regions without a reliable power supply. Therefore, nodes are usually equipped with batteries. In this scenario, energy becomes a scarce resource which must be carefully controlled. Energy-aware algorithms and protocols aim at extending network lifetime and performance by minimizing the energy consumption of all regular operations. In this paper we deal with one of these regular operations, namely broadcasting, which is the action of one sender node transmitting information (possibly in a multi-hop fashion) to all other nodes of the network. In this paper we deal with the minimum energy broadcast problem in sensor networks with realistic antennas (MEBRAs) which was introduced in [2]. This problem is a generalization of the classical minimum energy broadcast (MEB) problem from the literature [3]. In contrast to the assumption made in the MEB, real antennas are not able to transmit at any given transmission power, that is, any real value between 0 and the maximum one allowed by the hardware. Instead, real antennas usually have a set of fixed transmission power levels. For example, sensor node manufacturers such as Coalesenses GmbH (iSense) or Sun Microsystems (SunSPOTs) use antennas with six, respectively 200, transmission power levels (in addition to the state of turning the antennas off).

In this paper we dealt with the minimum energy broadcast problem in sensor networks with realistic antennas (MEBRAs). The MEBRA is a more realistic version of the minimum energy broadcast (MEB) problem, which has been extensively studied in the last decade. This work provided two contributions. The first one consists in a modified greedy function for the classical broadcast incremental power (BIP) heuristic. The second contribution is a distributed version of an ant colony optimization (ACO) algorithm proposed in the literature for the MEBRA problem. The proposed distributed ACO algorithm makes use of localized greedy information for constructing solutions. Moreover, the source node of the broadcast transmission is the pacemaker of the algorithm. Information about constructed solutions and the pheromone update is aggregated in the source node, which, in turn, triggers actions such as the construction of solutions and the update of the pheromone values. Concerning the results, we were able to observe that the distributed ACO algorithm generally outperforms the centralized classical BIP heuristic. This is a remarkable achievement, because the distributed version of BIP is significantly worse than the centralized version of BIP. When sensor nodes with few transmission power levels are considered, the results of the distributed ACO algorithm are even close to the results of the centralized ACO version. This changes when the number of available transmission power levels grows. In this case, the performance of the centralized ACO algorithm is significantly better than the one of the distributed ACO version. It is also worth pointing out that our distributed ACO algorithm uses a relatively low number of messages at each iteration, while keeping a rather low message size. Finally, the main advantage of the proposed distributed ACO algorithm over the centralized ACO version is the fact that it can be applied even when the structure of the network is unknown. This may be the case, for example, in outdoor applications concerning inhospitable environments. Future work will mainly be focused on two different aspects. The first one concerns the study of the changing performance of the algorithm depending on the number of transmission power levels available at each antenna. The second one will deal with an experimental evaluation of the algorithm on dynamically changing networks.