無線傳感器網(wǎng)絡(luò)節(jié)點移動路徑優(yōu)化方法

劉香愛，馮煙利

（1.山東師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 濟南250014；2.山東工商學(xué)院 計算機科學(xué)與技術(shù)學(xué)院，山東 煙臺264005）

0 引 言

覆蓋 問題是無線 傳 感 器 網(wǎng) 絡(luò)（wireless sensor networks，WSN）的基本問題。它反映了WSN對被監(jiān)測區(qū)域或目標(biāo)提供的感知服務(wù)能力。無線傳感器網(wǎng)絡(luò)在部署傳感器時通常采用隨機部署方式，所以覆蓋空洞的出現(xiàn)是避免不了的。這會使網(wǎng)絡(luò)的生存時間提前結(jié)束，網(wǎng)絡(luò)中會遺留大量未被利用的能量資源。所以，在保持網(wǎng)絡(luò)原有覆蓋水平的基礎(chǔ)上，有效地節(jié)能對傳感器網(wǎng)絡(luò)來說是非常重要的［1－6］。

在無線傳感器網(wǎng)絡(luò)中，覆蓋問題的最終目的是在不降低原有覆蓋水平的基礎(chǔ)上，有效分配各節(jié)點的狀態(tài)，最小化網(wǎng)絡(luò)每輪的能量消耗，同時使每個節(jié)點平均分擔(dān)網(wǎng)絡(luò)能耗［7］。所以在移動傳感器修復(fù)覆蓋空洞時，確定了移動傳感器的最后位置之后我們需要決定怎樣把傳感器移動到目標(biāo)位置才能達到更好的網(wǎng)絡(luò)覆蓋效果。文獻 ［9］中基本競標(biāo)協(xié)議采用直接移動（direct movement，DM）的方式，但它一般達不到網(wǎng)絡(luò)的應(yīng)用需求，浪費更多的時間，過度消耗單個傳感器的能量。在文獻 ［11］中提出用級聯(lián)移動（cascaded movement，CM）來優(yōu)化這個問題。文中詳細講述了選擇中間級聯(lián)節(jié)點的方法，但在選擇級聯(lián)移動路徑時，只考慮了路徑的總能耗，不能更好的均衡每個移動傳感器的能耗。怎么確定最優(yōu)的級聯(lián)移動路徑是一個值得考慮的問題。最優(yōu)的級聯(lián)移動路徑既要平衡各傳感器的能量消耗，又要減少路徑的總能耗。

本文針對這個問題，對文獻 ［11］中的級聯(lián)移動進行了改進，在選擇最優(yōu)級聯(lián)移動路徑時，用多目標(biāo)優(yōu)化的方法充分考慮了各傳感器間的能耗平衡。它通過減少單個傳感器的能量消耗，平衡網(wǎng)絡(luò)中傳感器的能量，提高了網(wǎng)絡(luò)的能量使用效率。

1 移動路徑的優(yōu)化

1.1 基本假設(shè)

本文基于以下假設(shè)：①傳感器一旦被部署，將會獨立工作，每個傳感器的能量不能補充，即當(dāng)其能量耗盡的時候，傳感器則不能工作，各傳感器初始能量均為E＞0；②所有傳感器節(jié)點的感知半徑和通信半徑均相等并都為圓盤形；③所有移動傳感器的移動速度均相等，用speed表示。

文中提出的改進的級聯(lián)移動（improved cascaded movement，ICM），首先采用文獻 ［11］的方法選擇中間級聯(lián)移動節(jié)點，再采用下面的方法選擇最優(yōu)的級聯(lián)移動路徑。

1.2 最優(yōu)路徑的選擇

為了平衡網(wǎng)絡(luò)中各傳感器的能耗，各移動傳感器的移動距離應(yīng)大致相等，則這里假設(shè)級聯(lián)移動路徑中的所有移動傳感器同時移動。

定義1在級聯(lián)移動路徑中，從任意移動傳感器（包括目的移動傳感器和所有中間級聯(lián)傳感器）開始移動到覆蓋空洞修復(fù)完成所花費的時間稱為路徑的移動時間。

假設(shè)某條有效的級聯(lián)移動路徑m中，中間級聯(lián)節(jié)點有n個，節(jié)點i的移動距離為dm，i。則路徑m的移動時間為

其中，Tm≤T。只有當(dāng)dm，i越小時，路徑m的移動時間才會越小，從而縮短網(wǎng)絡(luò)的恢復(fù)時間。

路徑m總的移動長度

式中：D——需移動的移動傳感器s0與目標(biāo)位置s之間的距離。

在路徑m上，傳感器節(jié)點i移動消耗的能量

式中：e——移動傳感器移動單位距離所消耗的能量。則節(jié)點i的剩余能量

移動傳感器節(jié)點i的能量可用率

路徑m的能量可用率

定義2決定性能量［12］：是指某條可用級聯(lián)移動路徑m上的所有節(jié)點的最小能量可用率，記作DEm

式中：i——路徑m上的第i個節(jié)點si。

從目的移動傳感器到目標(biāo)位置有多條可用的級聯(lián)移動路徑，需要從中選出一條最優(yōu)的移動路徑。設(shè)P＝｛DEm＞λ，m∈M｝，其中λ為閾值，M為所有可用路徑集。若則從P中選擇一條路徑能量可用率最大的路徑

否則，從集合M中選擇一條決定性能量DEm最大的路徑

根據(jù)式（9），式（10），可從所有可用路徑集M 中選出決定性能量大于閾值λ且路徑能量可用率最大或決定性能量最大的路徑，作為最優(yōu)級聯(lián)移動路徑。閾值λ的大小可由用戶根據(jù)實際應(yīng)用情況來確定，一般設(shè)置為0.3。

定義3多目標(biāo)優(yōu)化問題的數(shù)學(xué)形式一般可以描述為［13］

解決移動傳感器的級聯(lián)移動路徑問題提高網(wǎng)絡(luò)能量的使用效率就是最大化路徑的能量可用率或決定性能量。根據(jù)式（7），路徑的能量可用率ηm是由中間級聯(lián)節(jié)點的個數(shù)n和各節(jié)點的能量可用率ηm，i所決定的。而且在節(jié)點的能量可用率相對均等的情況下，路徑上的中間級聯(lián)節(jié)點數(shù)越多，ηm的值就越小。根據(jù)式（8），決定性能量DEm也是由各節(jié)點的能量可用率ηm，i所決定的。根據(jù)式（4）、（5）、（6），各節(jié)點的能量可用率ηm，i最終是由節(jié)點i的移動距離dm，i決定的。歸根結(jié)底，解決問題的根本就需要最小化中間級聯(lián)節(jié)點的個數(shù)n，并最小化各節(jié)點的移動距離。由式（2）、（3）可以看出，這是多目標(biāo)優(yōu)化問題。

如圖1所示，采用多目標(biāo)優(yōu)化方法，假設(shè)從目的移動傳感器s0到目標(biāo)位置s存在3條可用的級聯(lián)移動路徑，目的移動傳感器可以沿著任意一條路徑移動到目的位置。

圖1 級聯(lián)移動路徑

各節(jié) 點 的 能 量 可 用 率 ηm，i如 下：η1，A＝0.8；η1，B＝0.35；η2，C＝η2，D＝η3，G＝0.5；η3，E＝0.6；η3，F(xiàn)＝0.7；ηs0＝0.9。

則各級聯(lián)移動路徑的能量可用率ηm和決定性能量DEm分別如下：

路徑1：η1＝0.9×0.8×0.35＝0.252，決定性能量DE1＝0.35；

路徑2：η2＝0.9×0.5×0.5＝0.225，決定性能量為DE2＝0.5；

路徑3：η3＝0.9×0.6×0.7×0.5＝0.189，決定性能量為DE3＝0.5。

按照式（9）和（10）的路徑選擇規(guī)則，由于路徑2和路徑3的決定性能量DEm大于λ，因此最優(yōu)級聯(lián)移動路徑將在路徑2和路徑3中產(chǎn)生。其中，η2大于η3，所以路徑2成為傳感器移動修復(fù)覆蓋空洞的最優(yōu)路徑。從上面計算中可以看出，路徑1的ηm最大，然而由于DE1不大于λ，則路徑1被排除；路徑3上各節(jié)點的ηm，i雖然均大于或等于路徑2上的ηm，i，但是由于中間級聯(lián)節(jié)點數(shù)量較多，最后的η3小于η2。

由此，該級聯(lián)移動策略不僅保護了路徑上的低能量節(jié)點，而且考慮了節(jié)點平均剩余能量和較少的中間級聯(lián)節(jié)點個數(shù)作為路徑選擇的可行性。這樣，在目的移動傳感器進行移動修復(fù)WSN覆蓋空洞時，當(dāng)前能量均衡的、健壯的、中間級聯(lián)節(jié)點個數(shù)少的路徑就會勝出，成為移動傳感器的移動路徑，從而使傳感器間的能量消耗相對均衡，有效地延長網(wǎng)絡(luò)的生存時間。

2 仿真實驗

目標(biāo)區(qū)域是一個30 m×30 m的矩形，在區(qū)域內(nèi)隨機混合部署一定數(shù)量的移動節(jié)點和靜態(tài)節(jié)點。假設(shè)傳感器節(jié)點總數(shù)為50個，移動傳感器的百分比從10%變化到50%。實驗在目標(biāo)區(qū)域內(nèi)隨機產(chǎn)生不同大小的閉合的覆蓋空洞。通過仿真比較了CM與ICM在能量使用效率方面的性能。

在無線傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)能耗主要是由傳感器的移動和通信造成的。圖2比較了CM與ICM平均移動距離情況。CM只從總能耗方面選擇級聯(lián)移動路徑，至于涉及的移動傳感器的平均能耗不能得到優(yōu)化。移動傳感器的平均能耗主要是由它們的平均移動距離決定的。另外，由于ICM需要明確計算級聯(lián)移動路徑的能量，所以它的消息復(fù)雜度較之直接移動明顯增加了，如圖3所示。

但是，移動傳感器移動1m消耗30J能量，而發(fā)送1字節(jié)消息只消耗0.1J能量。也就是說，移動傳感器移動1m消耗的能量是發(fā)送1字節(jié)消息所耗能量的300倍。所以，在無線傳感器網(wǎng)絡(luò)中，消息復(fù)雜度對網(wǎng)絡(luò)能耗的影響極小，可以不予考慮。圖4給出了兩種移動方式下無線傳感器網(wǎng)絡(luò)能量使用效率隨移動傳感器所占比例的變化情況。無線傳感器網(wǎng)絡(luò)中能量使用效率與網(wǎng)絡(luò)生存時間密切相關(guān)。從而，級聯(lián)移動大大延長了網(wǎng)絡(luò)生存時間。

3 結(jié)束語

針對移動傳感器修復(fù)無線傳感器網(wǎng)絡(luò)中的覆蓋空洞問題，本文對級聯(lián)移動作了進一步的改進。在選擇級聯(lián)移動路徑時，通過節(jié)點的剩余能量精確計算了路徑的能量可用率，引入了路徑的決定性能量的概念，并結(jié)合了多目標(biāo)優(yōu)化的思想，充分考慮了各移動傳感器間的能耗平衡。它通過減少單個移動傳感器的能量消耗，平衡網(wǎng)絡(luò)中傳感器的能量，提高了網(wǎng)絡(luò)的能量使用效率。最后，通過仿真實驗驗證了改進方法的有效性和優(yōu)越性，網(wǎng)絡(luò)的能量使用效率得到明顯提高，延長了WSN的生存時間。

［1］Ghosh A，Sajal K D.Coverage and connectivity issues in wireless sensor networks：A survey ［J］.Pervasive and Mobile Computing，2008，4（3）：303－334.

［2］REN Yan，ZHANG Sidong，ZHANG Hongke.Theories and algorithms of coverage control for wireless sensor networks ［J］.Journal of Software，2006，17（3）：422－433（in Chinese）.［任彥，張思東，張宏科.無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法 ［J］.軟件學(xué)報，2006，17（3）：422－433.］

［3］Jennifer Yick，Biswanath Mukherjee，Dipak Ghosal.Wireless sensor network survey ［J］.Computer Networks，2008，52（12）：2292－2330.

［4］LIU Benyuan，Towsley D，Dousse O，et al.Mobility improves coverage of sensor networks ［C］.New York，USA：Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing，2005：300－308.

［5］Sudip Misra，Subhas Chandra Misra，Isaac Woungang.Guide to wireless sensor networks ［M］.London：Springer，2009：47－79.

［6］HU Yaofeng，ZHANG Jianming，WANG Xinsheng，et al.Research on energy－aware multi－path routing protocol in wireless sensor network ［J］.Computer Engineering and Design，2009，30（21）：4811－4814（in Chinese）. ［胡耀鋒，張建明，王新勝，等.能量感知的無線傳感器網(wǎng)絡(luò)多路徑路由研究 ［J］.計算機工程與設(shè)計，2009，30（21）：4811－4814.］

［7］MAO Yingchi，LIU Ming，CHEN Lijun，et al.A distributed energy－efficient location－independent coverage protocol in wire－less sensor networks ［J］.Journal of Computer Research and Development，2006，43（2）：187－195（in Chinese）. ［毛鶯池，劉明，陳力軍，等.DELIC：一種高效節(jié)能的與節(jié)點位置無關(guān)的傳感器網(wǎng)絡(luò)覆蓋協(xié)議 ［J］.計算機研究與發(fā)展，2006，43（2）：187－195.］

［8］WANG Bang，Hock B L，MA Di.A survey of movement strategies for improving network coverage in wireless networks［J］. Computer Communications， 2009， 32（13－14）：1427－1436.

［9］WANG Guiling，CAO Guohong，Berman P，et al.Bidding protocols for deploying mobile sensors［J］.IEEE Transactions on Mobile Computing，2007，6（5）：563－576.

［10］SU Han，WANG Yun.A self－h(huán)ealing algorithm without location information in sensor networks ［J］.Chinese Journal of Computers，2009，32（10）：1957－1970（in Chinese）.［蘇瀚，汪蕓.傳感器網(wǎng)絡(luò)中無需地理信息的空洞填補算法 ［J］.計算機學(xué)報，2009，32（10）：1957－1970.］

［11］WANG Guiling，CAO Guohong，TOM L P，et al.Sensor relocation in mobile sensor networks ［C］.Miami，F(xiàn)L，USA：INFOCOM，2005：2302－2312.

［12］FAN Zhigang.Research on coverage and node deployment in wireless sensor networks ［D］.Chengdu：University of Electronic Science and Technology of China，2008（in Chinese）.［凡志剛.無線傳感器網(wǎng)絡(luò)覆蓋與節(jié)點部署問題研究 ［D］.成都：電子科技大學(xué)，2008.］

［13］Sumanl B，Kumar P.A survey of simulated annealing as a tool for single and multiobjective optimization ［J］.Journal of the Operational Research Society，2006，57（10）：1143－1160.