Greedy Algorithms for Actor Redeployment in Wireless Sensor-Actor Networks

在無線傳感器網路利用貪婪演算法來達成傳感器的重新佈建

游振威(Chen-Wei Yu)

指導教授 ： 蔡明哲

國立清華大學/電機資訊學院/資訊工程學系/碩士(2011年)

https://doi.org/10.6843/NTHU.2011.00496

摘要

在無線傳感器網路(WSAN)中，當感測器(sensor)偵測到事件發生時，傳感器(actor)必須即時提供服務來處理事件。因此傳感器的佈建方式對於無線傳感器網路的效能有非常大的影響。在許多可能的情況下，傳感器會毀損，或是正忙於處理事件，因此無法繼續覆蓋原本的感測器，這時原本被傳感器覆蓋的感測器就無法即時將資料傳給傳感器。基於這個情況，我們需要將傳感器重新佈建。在這篇論文中，我們研究傳感器重新佈建的方法來達到最多感測器的覆蓋以及達到能減少最多沒被覆蓋感測器到最近有被覆蓋的感測器的距離。我們證明了這兩個問題的困難度都是NP-完全，並證明使用貪婪演算法來處理這兩個問題得到的答案與最佳解的比值都小於2。實驗也顯示出使用貪婪演算法可以達到夠好的效能，也佐證了我們的分析。

關鍵字

無線傳感器網路 ； 感測器覆蓋問題

並列摘要

Inawirelesssensor-actornetwork,anactorusuallyhastoprovideservicesassoonastheactorreceivestheeventsignalsfromthesensors.Therefore,theperformanceofawirelesssensor-actornetworkdependsontheactordeployment.Inmanycircum-stances,actorsmayfailorgoouttodealwithevents,andthus,thesensorscoveredbythemissingactorscouldbeunreachableintime.Thisintroducesthenecessityofactorredeployment.Inthispaper,westudytheproblemsofredeployingactorstomaximizethenumberofsensorsabletobecoveredbyactorsandtomaximizethedecreaseoftheresidualdistancesofsensors,respectively.BothproblemsareshowntobeNP-complete.Additionally,weprovethatthegreedyalgorithmforeachprob-lemhasanapproximationratioof2.Simulationsshowthatthegreedyalgorithmforeachproblemperformswell.Keywords:wirelesssensor-actornetwork,coverage

參考文獻

[1] T. Melodia, D. Pompili, and I. F. Akyildiz, “Handling mobility in wireless sensor and actor networks,” IEEE Transactions on Mobile Computing, vol. 9, pp. 160–173, 2010.

[2] I. A. Ismail, I. F. Akyildiz, and I. H. Kasimoglu, “Wireless sensor and actor networks: research challenges,” Ad Hoc Networks, vol. 2, pp. 351–367, 2004.

[3] K. Akkaya and M. Younis, “COLA: A coverage and latency aware actor placement for wireless sensor and actor networks,” in IEEE VTC, 2006, pp. 1–5.

[4] X.-P. Ren and Z.-X. Cai, “A distributed actor deployment algorithm for maximum connected coverage in WSAN,” in ICNC, 2009, pp. 283–287.

[5] K. Akkaya and S. Janapala, “Maximizing connected coverage via controlled actor relocation in wireless sensor and actor networks,” Computer Networks, vol. 52,