曹先波

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

0 引言

近年來，無線傳感器網(wǎng)絡(luò)（Wireless Sensor Net?works，WSNs）受到了世界各國(guó)的廣泛關(guān)注，特別是隨著微電子機(jī)械系統(tǒng)（MEMS）技術(shù)的進(jìn)步，促進(jìn)了智能傳感器的發(fā)展。這些傳感器節(jié)點(diǎn)可以感知、測(cè)量和收集來自環(huán)境的信息，然后，基于某種局部決策過程，將感測(cè)到的數(shù)據(jù)發(fā)送給用戶。由于應(yīng)用場(chǎng)景不同，傳感器也因此種類繁多，針對(duì)不同的感知信息，可以使用不同類別的傳感器。感知的信息主要包括：濕度、溫度、壓力、強(qiáng)度等等信息。多數(shù)傳感器主要是由傳感器模塊、處理器模塊、能量供應(yīng)模塊和無線通信模塊組成。傳感器模塊感知周圍環(huán)境信息，處理器模塊協(xié)調(diào)各個(gè)模塊之間的工作關(guān)系，控制各模塊工作模式。能量供應(yīng)模塊為傳感器提供能量，保證傳感器的正常運(yùn)行。無線通信模塊負(fù)責(zé)與其他傳感器之間的通信工作，接收從其他傳感器傳輸過來的數(shù)據(jù)，處理后發(fā)送給其他的傳感器或基站。

無線傳感器網(wǎng)絡(luò)通常由多個(gè)傳感器節(jié)點(diǎn)組成，共同監(jiān)視一個(gè)區(qū)域，以獲取有關(guān)環(huán)境的數(shù)據(jù)。無線傳感器網(wǎng)絡(luò)一般可分為兩種類型：結(jié)構(gòu)化和非結(jié)構(gòu)化。在非結(jié)構(gòu)化無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)隨機(jī)部署在需要監(jiān)視的區(qū)域。部署以后，網(wǎng)絡(luò)將以無人看管的方式執(zhí)行監(jiān)視和報(bào)告的任務(wù)。這種非結(jié)構(gòu)化類型的無線傳感器網(wǎng)絡(luò)由于節(jié)點(diǎn)太多，網(wǎng)絡(luò)維護(hù)（如連接管理和故障檢測(cè)）會(huì)非常困難。在結(jié)構(gòu)化無線傳感器中，所有或部分傳感器節(jié)點(diǎn)都是以預(yù)先計(jì)劃的方式部署的。這使得結(jié)構(gòu)化類型的無線傳感器網(wǎng)絡(luò)可以部署更少的節(jié)點(diǎn)，降低網(wǎng)絡(luò)維護(hù)和管理成本。

在應(yīng)用方面，無線傳感器網(wǎng)絡(luò)應(yīng)用于軍事目標(biāo)跟蹤和監(jiān)視，自然災(zāi)害救濟(jì)，生物醫(yī)學(xué)健康監(jiān)測(cè)、危險(xiǎn)環(huán)境探索以及地震感應(yīng)等多個(gè)領(lǐng)域。在軍事目標(biāo)跟蹤和監(jiān)視中，無線傳感器網(wǎng)絡(luò)可以協(xié)助進(jìn)行入侵檢測(cè)和識(shí)別。具體示例包括與空間相關(guān)且協(xié)調(diào)的部隊(duì)和坦克運(yùn)動(dòng)。對(duì)于自然災(zāi)害，傳感器節(jié)點(diǎn)可以感知并檢測(cè)環(huán)境，以在災(zāi)害發(fā)生之前進(jìn)行預(yù)測(cè)。在生物醫(yī)學(xué)應(yīng)用中，傳感器的外科植入物可以幫助監(jiān)測(cè)患者的健康狀況。對(duì)于地震感應(yīng)，沿著火山區(qū)域臨時(shí)部署傳感器可以收集地震和爆發(fā)的數(shù)據(jù)。

然而，目前無線傳感器網(wǎng)絡(luò)通過電池進(jìn)行供電，電池能量有限這一特點(diǎn)使得網(wǎng)絡(luò)的運(yùn)行壽命受到限制。部分研究者[1-2]提出從環(huán)境中采集能量供傳感器使用，例如：太陽能、風(fēng)能等，以延長(zhǎng)傳感器的壽命。然而這種方式具有很大的不確定性，受到周圍環(huán)境的嚴(yán)重影響。例如，使用太陽能為傳感器供電將不得不受到天氣的影響，太陽能的能量收集效率在雨天會(huì)比晴天達(dá)到數(shù)十倍差距。另外，隨著無線能量傳輸技術(shù)的發(fā)展[3]，利用攜帶無線充電設(shè)備的移動(dòng)充電小車為傳感器節(jié)點(diǎn)補(bǔ)充能量，延長(zhǎng)無線傳感器網(wǎng)絡(luò)的壽命的充電研究，吸引了很多學(xué)者。這種方式更加可控、高效且對(duì)環(huán)境的依賴性更低。本文針對(duì)小規(guī)模的無線傳感器網(wǎng)絡(luò)，提出兩種移動(dòng)充電小車的充電節(jié)點(diǎn)選取算法。

1 網(wǎng)絡(luò)模型

在一個(gè)給定的二維平面上，隨機(jī)部署N個(gè)傳感器節(jié)點(diǎn)，這些傳感器節(jié)點(diǎn)表示為s={s1,s2,…,sn} ，基站表示為s0。每個(gè)傳感器節(jié)點(diǎn)si∈S都是由能量為bi的電池供電，i=1,2,…,N。傳感器節(jié)點(diǎn)通過感應(yīng)、接收和發(fā)送數(shù)據(jù)消耗能量，假定傳感器si的能量消耗速率和剩余能量分別表示為eci和rei。傳感器節(jié)點(diǎn)si和sj之間的距離為di,j，移動(dòng)充電小車每移動(dòng)一單元距離消耗c的能量。如圖1所示，在一個(gè)充電周期中，移動(dòng)充電小車從基站s0出發(fā)，沿著充電路徑為傳感器節(jié)點(diǎn)補(bǔ)充能量，最后回到基站s0為下一個(gè)周期做準(zhǔn)備。過程中，移動(dòng)充電小車的移動(dòng)速度為v。本文研究了在小規(guī)模的無線傳感網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)的選擇問題，找到移動(dòng)充電小車的充電路徑C。

為了便于表述問題，本文將充電的網(wǎng)絡(luò)模型構(gòu)建成一個(gè)網(wǎng)絡(luò)圖G=(S,E,D)，其中，S是網(wǎng)絡(luò)中的傳感器集合，E是網(wǎng)絡(luò)中傳感器之間的邊的集合，D是代表E的權(quán)重，即傳感器之間的歐幾里得距離。

圖1

2 充電模型

在無線可充電傳感器網(wǎng)絡(luò)中，傳感器裝配能量有限且可以進(jìn)行無線能量傳輸?shù)碾姵兀瓿蓴?shù)據(jù)感應(yīng)、數(shù)據(jù)收集和數(shù)據(jù)發(fā)送工作。為了能夠保持網(wǎng)絡(luò)正常且長(zhǎng)時(shí)間的運(yùn)行，需要及時(shí)為傳感器補(bǔ)充能量，一種常用的做法是在網(wǎng)絡(luò)中加入攜帶無線充電設(shè)備的移動(dòng)充電小車為傳感器進(jìn)行無線能量傳輸。本文中，移動(dòng)充電小車從基站出發(fā)，以恒定的速率移動(dòng)到選取的傳感器附近，通過無線能量傳輸為傳感器補(bǔ)充能量。

移動(dòng)充電小車離開基站，經(jīng)過（s1,s2,…,sn），最后回到基站，于是移動(dòng)充電小車的總行駛距離可以表示為：

3 能耗模型

傳感器在網(wǎng)絡(luò)中的能量消耗主要集中在數(shù)據(jù)感應(yīng)、數(shù)據(jù)接收和數(shù)據(jù)發(fā)送方面，因此傳感器si的能量消耗可以表示為：

其中，us是傳感器感應(yīng)一單位數(shù)據(jù)需要消耗的能量，ri是傳感器si感應(yīng)數(shù)據(jù)的速率。傳感器si的數(shù)據(jù)發(fā)送消耗的能量表示為：

其中，N(si)表示在網(wǎng)絡(luò)G中，傳感器si的鄰居傳感器集合，是傳感器si發(fā)送一單位數(shù)據(jù)給傳感器sj所消耗的能量，fij是傳感器si到傳感器sj傳輸?shù)臄?shù)據(jù)量。對(duì)于傳感器的數(shù)據(jù)接收的能量消耗可以表示為：

其中，ur是傳感器接收一單位數(shù)據(jù)所需要消耗的能量，fji是傳感器si接收來自傳感器sj的數(shù)據(jù)量。

4 問題描述

本文研究了一個(gè)具有N個(gè)傳感器的無線傳感器網(wǎng)絡(luò)中的傳感器選取問題，最終得到移動(dòng)充電小車的閉合充電回路C。為了提高移動(dòng)充電小車所攜帶的電池能量，減少網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)因?yàn)槟芰亢谋M而死亡，影響網(wǎng)絡(luò)的性能。針對(duì)這兩個(gè)方面的內(nèi)容，本文提出了兩個(gè)算法來進(jìn)行討論。

5 算法描述

在算法一（Sensor Selection Algorithm based on Ant Colony Optimization，SSAACO）中，為了盡可能提高移動(dòng)充電消息的能量利用效率，需要減少移動(dòng)充電小車的行駛距離，即式（1）所示。于是本文將充電小車的傳感器選取問題轉(zhuǎn)化為經(jīng)典的TSP旅行商問題，構(gòu)造最短的哈密爾頓環(huán)作為移動(dòng)充電小車的行駛路徑，以使路徑最短，提高小車的能量利用效率。然而尋找到最短的哈密爾頓回路是NP難問題，所有可能的路徑數(shù)量是n!，計(jì)算的時(shí)間復(fù)雜度非常高，無法在多項(xiàng)式時(shí)間內(nèi)得到最優(yōu)解。隨著傳感器的數(shù)量增多，基本上已經(jīng)無法完成最優(yōu)解的計(jì)算。為了在可接受的時(shí)間內(nèi)找到結(jié)果，本文利用蟻群算法的優(yōu)點(diǎn)，通過迭代的方式得到移動(dòng)充電小車的最佳行駛路徑。

在算法二中（Least Energy Sensor Selection Greedy Algorithm，LESSGA），文章考慮到有些傳感器的能量比較少，需要及時(shí)補(bǔ)充能量。為了滿足傳感器的急迫性需求，本文利用貪心策略，當(dāng)移動(dòng)充電小車選取下一個(gè)傳感器的時(shí)候，計(jì)算當(dāng)前環(huán)境中所有傳感器的能量狀態(tài)信息，將能量最少的傳感器作為下一個(gè)待充電傳感器。傳感器si的剩余能量可以表示為：

其中，rei是傳感器si的剩余能量，tci是傳感器si上次補(bǔ)充能量的時(shí)間，ti是移動(dòng)充電小車到達(dá)傳感器si的時(shí)間。ti可以表示為：

其中，μ是移動(dòng)充電小車的能量傳輸效率，v是移動(dòng)充電小車的移動(dòng)速度。通過貪心策略，每次選取的傳感器加入C中，最后得到移動(dòng)充電小車的充電回路路徑。

6 實(shí)驗(yàn)結(jié)果與分析

本文在這一小節(jié)利用仿真實(shí)驗(yàn)進(jìn)行算法驗(yàn)證。10-30個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署在50m×50m的二維空間，移動(dòng)充電小車的移動(dòng)速率是5m/s，能量傳輸效率是5W。每個(gè)傳感器由3.7V/450mAh的堿性可充電電池供電，因此，傳感器的最大電池容量為3,7V×0.45A×3600sec=6kJ，傳感器的能量消耗隨機(jī)分布在0.1J/s-1J/s之間。

圖2

圖3

仿真實(shí)驗(yàn)結(jié)果如圖2和圖3所示，對(duì)比了文章提出的SSAACO算法、LESSGA算法以及沒有使用調(diào)度算法的None。如圖2所示，隨著傳感器節(jié)點(diǎn)數(shù)量的增加，移動(dòng)充電小車的路徑相應(yīng)增加。SSAACO算法能夠?yàn)槌潆娦≤嚨玫阶疃痰男旭偮窂?，且明顯小于LESS?GA算法和None。在移動(dòng)充電小車傳輸給傳感器的能量方面，LESSGA算法每次尋找能量最少的傳感器，使得整個(gè)充電周期時(shí)長(zhǎng)最長(zhǎng)，傳輸給傳感器的能量也最多。

7 結(jié)語

本文介紹了在可充電無線傳感器網(wǎng)絡(luò)中，如何調(diào)度移動(dòng)充電小車為傳感器補(bǔ)充能量，傳感器的選取問題。本文在針對(duì)希望減少移動(dòng)充電小車的行駛路徑方面和滿足傳感器的急迫性需求方面提出了兩種算法，并最后通過模擬實(shí)驗(yàn)證明了算法的有效性。