劉香愛，馮煙利

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

0 引 言

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

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

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

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

1.1 基本假設(shè)

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

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

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

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

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

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

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

路徑m總的移動(dòng)長(zhǎng)度

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

在路徑m上，傳感器節(jié)點(diǎn)i移動(dòng)消耗的能量

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

移動(dòng)傳感器節(jié)點(diǎn)i的能量可用率

路徑m的能量可用率

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

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

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

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

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

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

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

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

圖1 級(jí)聯(lián)移動(dòng)路徑

各節(jié) 點(diǎn) 的 能 量 可 用 率 η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。

則各級(jí)聯(lián)移動(dòng)路徑的能量可用率η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)級(jí)聯(lián)移動(dòng)路徑將在路徑2和路徑3中產(chǎn)生。其中，η2大于η3，所以路徑2成為傳感器移動(dòng)修復(fù)覆蓋空洞的最優(yōu)路徑。從上面計(jì)算中可以看出，路徑1的ηm最大，然而由于DE1不大于λ，則路徑1被排除；路徑3上各節(jié)點(diǎn)的ηm，i雖然均大于或等于路徑2上的ηm，i，但是由于中間級(jí)聯(lián)節(jié)點(diǎn)數(shù)量較多，最后的η3小于η2。

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

2 仿真實(shí)驗(yàn)

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

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

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

3 結(jié)束語

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

［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é)報(bào)，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］.計(jì)算機(jī)工程與設(shè)計(jì)，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é)點(diǎn)位置無關(guān)的傳感器網(wǎng)絡(luò)覆蓋協(xié)議 ［J］.計(jì)算機(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ò)中無需地理信息的空洞填補(bǔ)算法 ［J］.計(jì)算機(jī)學(xué)報(bào)，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é)點(diǎn)部署問題研究 ［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.