在無線感測網路中考慮覆蓋生命週期之群體智慧的佈置策略

Swarm Intelligence Based Deployment Protocol on Lifetime Sensing Coverage for Wireless Sensor Networks

吳如婷(Ru-Ting Wu)

指導教授 ： 高有成 ； 廖文華

大同大學/經營設計學院/資訊經營學系所/碩士(2009年)

摘要

感測器的佈置是一個重要的議題，因為它能夠反映出無線感測網路的花費成本與感測能力。覆蓋能力在無線網路中也是一個重要的監測品質。螞蟻演算法應用在多重背包問題，利用螞蟻本身自然的特性去探尋可能的解。在本論文中，將考慮感測器佈置的完整覆蓋與網路存活時間最大化的問題。首先將感測器佈置的覆蓋公式化成類似於多重背包的問題，再以螞蟻演算法為基礎，來提出一個延長網路存活時間及確保完整覆蓋的佈置策略。最後實驗結果顯示，本論文的方法確實可以有效延長網路的存活時間。

關鍵字

感測器佈置 ； 覆蓋 ； 螞蟻演算法 ； 存活時間

並列摘要

Sensor deployment is a critical issue since it reflects the cost and detection capability of a wireless sensor network. Coverage is also important in quality of monitoring in wireless sensor networks. Ant colony optimization (ACO) algorithm provides natural and intrinsic way of exploration of search space in multiple knapsack problem (MKP). In this work, we consider the problem of sensor deployment to full the coverage and maximize the lifetime of the network. We will formulate the deployment of sensors for coverage to the multiple knapsack like problem. Based on ACO algorithm, our paper proposed a deployment strategy to prolong the network lifetime, while ensuring a full coverage. The simulations have shown that our algorithm can prolong the lifetime of the network.

並列關鍵字

sensor deployment ； coverage ； Ant colony optimization (ACO) ； lifetime.

參考文獻

[2]M. Cardei, Y. Yang, and J. Wu, “Non-uniform Sensor Deployment in Mobile Wireless Sensor Networks,” IEEE World of Wireless, Mobile and Multimedia Networks (WoWMoM), pp. 1-8, 2008.

[3]M. Dorigo and L. M. Gambardella, “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53-66, Apr. 1997.

[4]C.-F. Huang and Y.-C. Tseng, “The Coverage Problem in a Wireless Sensor Network,” ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), pp. 115–121, 2003.

[5]C.-H. Liu and K.-F. Ssu, “A Moving Algorithm for Non-Uniform Deployment in Mobile Sensor Networks,” ACM Mobile Technology, Applications, and Systems, 2008.

[6]W.-H. Liao, Y. Kao, and C.-M. Fan, “Data Aggregation in Wireless Sensor Networks Using Ant Colony Algorithm,” Journal of Network and Computer Applications, Vol. 31, No. 4, pp. 387-401, 2008.