A Solution to Minimum Deployment Cost in Wireless Sensor Networks

在無線感測網路下最低佈建成本的一個解法

陳亭亦(Ting-Yi Chen)

指導教授 ： 金仲達

國立清華大學/電機資訊學院/資訊系統與應用研究所/碩士(2008年)

摘要

Suppose we need to deploy a wireless sensor network for collecting data to a sink node in a rural area that guarantees to run for a given lifetime. The specific points to deploy the sensor nodes are known. Suppose further that the battery of a sensor node cannot last for that long and the only means to achieve the required lifetime is to deploy redundant sensor nodes at each deployment point. The problem is: what the minimum number of sensor nodes is to meet the given lifetime. In this thesis, we solve this optimization problem. We will model the network as a graph G = (V, E), where vertices are the spots (deployment points) to deploy sensor nodes and edges indicate reliable wireless communications between the two end vertices. Since sensed data are transmitted to the sink node through a data gathering mesh, a solution to the above problem must consider how data are routed in the mesh. Therefore, our solution comes in two steps: one is an energy-aware forwarding scheme (EAF) that selects forwarding paths with the least deployment cost, and the second is a refinement heuristic to improve the initial solution by reallocating the traffic load. We evaluate our algorithm through random network with various sizes. Our solutions are compared with, and are close to corresponding lower bounds. Additional, our algorithm successfully minimize the remaining energy , or the waste of networks.

關鍵字

無線感測網路 ； 佈建成本

並列摘要

HASH(0x1d343580)

並列關鍵字

Wireless Sensor Network ； Deployment Cost

參考文獻

[1] J-H. Chang, and L. Tassiulas, “Maximum lifetime routing in wireless sensor networks, IEEE/ACM Trans. on Networking, 12(4): 609-619, Aug. 2004.

[2] J. Pan, Y. T. Hou, L. Cai, Y. Shi, and S. Shen, Topology control for wireless sensor neworks, Proc. ACM MOBICOM2003, pp. 286-299.

[3] Kenan Xu Hassanein, H. Takahara, G. Relay node deployment strategies in heterogeneous wireless sensor networks: multiple-hop communication case. IEEE Sensor and Ad Hoc Communications and Networks, 2005.

[4] K. Xu, Q. Wang, H. Hassanein, G. Takahara, Optimal wireless sensor networks (WSNs) deployment: minimum cost with lifetime constraint, IEEE Wimob 2005.

[5] M. Bhardwaj, T. Garnett, and A. P. Chandrakasan, Upper bounds on the lifetime of sensor networks, Proc. IEEE ICC2001, pp. 785-790.