Discovering Adaptive Heuristics for Ad-Hoc Sensor Networks by Mining Evolved Optimal Configurations

Ad-hoc sensor networks comprising large numbers of randomly deployed wireless sensors have recently been an active focus of investigation. These networks require self-organized configuration after deployment, and ad-hoc heuristic methods for such configuration have been proposed with regard to many aspects of the networks´ performance. However, systematic approaches for such configuration remain elusive. In this paper, we present a preliminary attempt towards such a systematic approach using evolutionary algorithms and reverse engineering. In particular, we focus on the problem of obtaining heterogeneous networks that optimize global functional properties through local adaptive rules. Almost all work on ad-hoc sensor network has so far involved homogeneous networks where all nodes transmit with the same power level, creating a symmetric connectivity. It is possible to construct heterogeneous networks by allowing nodes to transmit at different power levels, and such networks are known to provide improvements in network lifetime, power efficiency, routing, etc. However, such networks are difficult to build mainly because the optimal power level for each node depends on the node location and spatial context, which are not known before deployment. A few heuristic schemes focused on improving power consumption have been proposed in the literature, but the issue has not been investigated sufficiently at a general level. In this paper, we present a new and improved heuristic developed using a reverse engineered approach. A genetic algorithm is used to generate a set of heterogeneous sensor networks that are characterized by low short paths and minimal congestion. Analysis of this optimal network set yields rules that form the basis for a local heuristic. We show that networks adapted using this heuristic produce significant improvement over the homogeneous case. More importantly, the results validate the utility of the proposed approach that can be used in other self-orga- nizing systems.