Distributed and Asynchronous Solution to Operator Placement in Large Wireless Sensor Networks

Due to energy limitation of wireless sensor networks, in-network aggregation and distributed data fusion are proposed to perform the desired aggregation (or fusion) operators en route-eliminating data redundancy, minimizing transmissions and thus saving energy. An operator involved with in-network processing will be placed on a network node, which receives the data from sources, process them and send the output to either the next operator or sink node. As transmitting data from one operator to other imposes a cost, which is dependent on the placement of operators, the placement of operators can greatly affect the energy cost of in-network processing. In this research work, we propose a minimum-cost forwarding based asynchronous algorithm (MCFA) to find the optimal placement for operator tree with minimized energy cost of in-network processing. It is shown that minimum-cost forwarding can dramatically reduce message overhead of asynchronous algorithm. It is also shown that MCFA has less message overhead than synchronous algorithm by both mathematical analysis and simulation-based evaluation. For a regular grid network and a complete binary operator tree, the messages sent at each node are O(root NM) for MCFA, meanwhile O(root NM log(2) M) for synchronous algorithm, where N is the number of network nodes and M is the number of data objects in operator tree.