基于相遇位置預測的移動傳感器網絡能量補充方法研究

鄒英華,馮 勇,戴斌輝,王成棟

(昆明理工大學云南省計算機技術應用重點實驗室,昆明 650500)

由于無線移動傳感器網絡中的傳感器具有移動能力,能夠完成動態跟蹤等任務,被應用于氣體源定位[1]、災難救助[2]等方面。因此逐漸受到了學術界和工業界的關注[3-4]。

目前,傳感器網絡主要是由電池進行供電,而且在特殊的環境下人為地更換電池難以實現,能量問題便成為限制移動傳感器網絡廣泛應用的重要約束和挑戰,所以有研究工作者提出了節省能量的辦法[5],但是此方法不能從根本上解決問題,它只能有限的延長網絡壽命,當有傳感器的電量耗盡后,將有可能導致整個網絡無法正常工作。從周圍的環境中獲取能量也是一種辦法[6],但能量獲取過程具有高度的不可預測性和不可控性等缺點。無線充電技術[7]能主動提供高效、及時的充電服務。因此有研究工作者提出了利用固定充電站[8]給傳感器進行能量補充的方法,此方法需要傳感器額外地移動得到能量補充,使得其當前的任務不能及時完成。

利用移動充電裝置MC(Mobile Charger)給移動傳感器進行能量補充是一種十分有效的方法。MC主要使用了無線能量傳輸技術,例如電感耦合技術[9]、全向/定向電磁輻射技術[10]等。此技術可以給移動傳感器提供可靠、持續的能量補充。有研究者提出使用多個MC給傳感器進行能量補充[11-12],但由于MC價格不菲,在固定的區域中布置過多的MC給傳感器充電并不現實,所以如何合理、有效地規劃MC的充電路徑,成為一個非常棘手的問題。對此本文通過預測移動傳感器和MC的相遇位置使得傳感器在最短的時間內得到能量補充,并且MC可以獨立地完成充電任務。在保證傳感器工作效率的同時此方法還縮短了充電延遲,提高了充電效率。

1 相關工作

相對節能方法的有限性和能量收集方法的不可預測性,無線充電方法可以有效地保證充電的及時性。與部屬靜態的充電站相比,使用MC可以增強充電過程的靈活性和可控性。

文獻[13]提出了一種基于虛擬骨干網環境下的移動能量補充策略。此策略根據待充電傳感器當前的通信量計算優先級,給優先級最大的傳感器充電。文獻[14]提出了一種基于傳感器最大可容忍充電延遲的饑餓避免移動能量補充算法。由于靜態傳感器網絡與移動傳感器網絡組成成分的相似性,上述靜態傳感器網絡能量補充方法給了本文很多啟發。

文獻[15]提出分層團隊的方法,側重于支持多個機器人和MC對接進而補充能量。MC不斷優化其位置,減少團隊額外移動成本。雖使用了MC給機器人充電,但機器人需要中斷當前的任務來補充能量。文獻[16]中,當機器人的能量值達到閾值時,便會停止移動,等待MC給其充電。此方法雖不需要機器人額外地移動但不能從根本上解決機器人的工作效率得不到保證的問題。由于這些限制,將以上三種方法用在移動傳感器網絡能量補充方面也存在同樣的問題。因而又有研究者提出利用MC獨立地與傳感器會合進行能量補充的方法。

文獻[17]提出了機會主義的無線充電方式,通過相遇時間等信息在傳感器中選出錨點,這些錨點定期地回基站進行補充能量,并且在與剩余的傳感器相遇時給其補充能量。文獻[18]中,使用The Best-Effort Charging Schedule確定了MC和每個提出充電請求的機器人傳感器可能相遇的位置及可能的充電完成位置后,構造了一顆加權旅行樹。按旅行樹的單源最短路徑給傳感器充電,使得到的充電成本能盡可能小。并與算法The Best-Effort Charging Schedule做了對比,在充電成本方面有一定的優勢。

因此本文預測到MC和傳感器的相遇位置并對傳感器得到能量補充的優先級進行了深入的研究,在考慮了移動傳感器得到充電請求響應公平性問題的前提下,提出了一種相遇時間優先的能量補充策略。

2 網絡模型與問題陳述

2.1 網絡模型

在整個無線傳感器網絡中有I個移動的傳感器,S={s1,s2,si,…,sI},si代表編號為i的傳感器、一個MC、一個初始位置、M個目標位置,L={l1,l2,lm,…,lM},lm代表編號為m的目標位置。MC是一個具有自主移動能力和計算、通信能力的機器人,配有大容量的電池,并作為整個移動傳感器網絡中的能量傳輸者。每個傳感器配備有一個具有快速充電能力的可充電電池,和一個無線能量接收裝置,接收來自MC的能量。

移動傳感器部署在m×m的區域內以速度vs執行其任務。一輛MC以速度vc(vc>vs)給傳感器補充能量。令Einitial代表傳感器的總能量,θ代表剩余能量閾值,當其自身的剩余能量低于θEinitial時,便會發送充電請求,R={r1,r2,rn,…,rN}(N

圖1 網絡模型圖

本文提出的能量補充算法特別提出以下兩點:①MC在和傳感器相遇時會自動降低速度和傳感器同步移動進行能量補充;②在充電過程中,MC可以獨立地完成充電任務。

2.2 問題陳述

使用MC和傳感器相配合的方式給傳感器補充能量在緊急搜救等關鍵任務中也會造成不可逆轉的損失。MC獨立地與傳感器會合是一種更合適的能量補充方式。例如The Tree-based Charging Schedule方法中,MC根據單源最短路徑依次給相應的傳感器補充能量。其中MC是按傳感器提出充電請求的順序給其補充能量的,此種方式缺少一定的靈活性和實時性。從而增加了整體的充電延遲和充電成本。如圖2(a)MC是按照傳感器提出充電請求的順序給傳感器補充能量的,首先和第一個提出充電請求且距離較遠的傳感器1在B點相遇,C點充電完成,接著與傳感器2在D點相遇,E點充電完成。如圖2(b)MC優先選擇相遇時間短的傳感器2在B′點相遇,C′點充電完成,接著與傳感器1在D′點相遇,E′點充電完成,可以看出2(b)中的方式對縮短充電成本有一定的優勢。但始終選擇相遇時間短的傳感器不免會導致有些傳感器由于長時間得不到充電而失效。因此在考慮了移動傳感器得到充電請求響應公平性問題的前提下,提出了一種相遇時間優先的能量補充算法。此算法綜合考慮了整體充電延遲和充電公平性兩方面因素。本文中所使用的符號見表1。

圖2 充電成本對比圖

參數符號參數意義N網絡中移動傳感器的總數目Einitial→i移動傳感器的初始能量Ew工作狀態下每秒消耗的能量Es休眠狀態下每秒消耗的能量Eresidual→i(t)i的剩余能量cMC的充電速度vcMC的移動速度vs移動傳感器的移動速度ri(t)傳感器i的能量消耗率Tα→i,Tβ→iMC移動到傳感器i所需要的時間

3 相遇時間優先的充電算法

3.1 系統工作過程

移動傳感器剩余能量小于閾值時,向MC發送充電請求的消息包括:傳感器i的標識、剩余能量及傳感器的位置。

MC擁有一個可以接收充電請求的服務池。當它接收到充電請求后發現服務池中沒有來自該傳感器的請求,則增加一條記錄,若已有則更新其信息。初始時MC為空閑狀態,一旦MC和傳感器相遇,開始充電,其狀態將轉換為繁忙狀態。在空閑狀態,若有得到能量補充的優先級更高的傳感器請求充電,那么搶斷發生。只有空閑狀態才可發生搶斷,繁忙狀態不可被搶斷,待充電結束后MC重新切換為空閑狀態,選擇下一個充電目標,如此往復。

3.2 相遇位置的預測

若相遇位置在傳感器的移動軌跡上,在傳感器不中斷當前任務的前提下,MC和傳感器剛好相遇的位置為最佳位置。介紹以下預測MC和傳感器相遇位置的方法。

圖3 MC和移動傳感器相遇情況示意圖

圖3中定義MC的位置為C(xc,yc),傳感器的位置為S(xs,ys),目標位置為M(xm,ym),初始位置為O(xo,yo),MC與傳感器相遇位置為Eδ(xδ,yδ)或Eε(xε,yε)。若只有一個傳感器提出充電請求,MC就會向相遇位置移動。首先判斷傳感器的狀態為0(傳感器向目標位置移動的狀態)還是為1(傳感器向初始位置移動的狀態)。如圖3(a),當傳感器的狀態為0時,得到cosα為:

(1)

如圖3(b),當傳感器的狀態為1時,得到cosβ為:

(2)

此時根據式(1)和式(2)可以計算出當傳感器的狀態為0或1時,MC和提出充電請求的傳感器相遇所需要的時間分別為:

(3)

(4)

其中vs為傳感器的移動速度;vc為MC的移動速度(vc>vs)。

如圖3(a)中的星型和3(b)中的星型所示,當傳感器的狀態為0或1時,根據式(3)和式(4)得到MC與傳感器的相遇位置分別為:

(5)

(6)

此時MC會移動向傳感器的相遇位置Eδ(xδ,yδ)或Eε(xε,yε)與傳感器會合,進而補充能量。

3.3 確定下一個得到充電服務的傳感器

若只有一個傳感器提出充電請求,MC會與該傳感器在相遇位置匯合補充能量。但當有多個傳感器提出充電請求時,MC和傳感器的相遇時間越短,該傳感器得到充電服務的優先級越高,這樣的充電方式可以縮短充電延遲。但是如果單純的優先考慮給所有傳感器中相遇時間最短的傳感器充電,也會導致有些剩余能量很少并且和MC相遇時間較長的傳感器得不到及時的充電而失效,因此我們考慮了缺電移動傳感器得到充電請求響應的公平性問題,具體提出以下解決方案。下一個得到充電傳感器的選擇算法步驟如下。

第一步:如果服務池中存在且只有一個傳感器提出充電請求,MC來得及給該傳感器充電則向與該傳感器匯合的位置移動,為其充電。否則轉向第二步。

第二步:如果服務池中有多個傳感器,則計算每個傳感器與MC的相遇時間,將相遇時間從小到大對應的傳感器排序。此時按序遍歷服務池中的傳感器,若MC與傳感器相遇所需時間大于傳感器當前的生存時間,即MC優先移動向該傳感器相遇位置也避免不了該傳感器失效,則從服務池中將該傳感器刪除。表達式如下:

(7)

ts為傳感器提出充電請求時的時間,t為當前時間,Eresidual→i(t)為傳感器的剩余能量,ri(t)為傳感器i的能量消耗率,st為移動傳感器的狀態。

第三步:從服務池中第一個傳感器開始,優先給當前傳感器充電,將其余傳感器作為下一個充電傳感器時,若其等待充電的時間大于當前生存時間,則會導致其余傳感器停止工作。其中下一個充電傳感器需要等待的時間為:

(8)

(9)

Einitial→i為傳感器初始能量,c為充電速度,tm為給當前傳感器充電完成到與下一個傳感器相遇的時間。接著遍歷服務池,直到不滿足上述條件,即給當前傳感器充電完成后不會導致其余傳感器能量耗盡而失效。此時MC會選擇當前傳感器給其充電。當前傳感器即為下一個得到充電服務的傳感器。在極端情況下,遍歷完整個服務池都沒有符合條件的充電傳感器,則轉向第四步。

第四步:此時MC選擇相遇時間最短的傳感器為下一個得到充電服務的傳感器。

如圖4,有7,2,5號三個傳感器依次請求充電,按相遇時間從小到大給相應的傳感器排序5,2,7。即使MC優先給7號充電也避免不了7號的失效,則不考慮給7號傳感器充電。因此判斷優先給5號充電,由于2號剩余能量過少,給五號傳感器充電完成后則會導致2號停止工作,所以也暫時先不給5號充電。再判斷優先給2號充電,此時不會導致其余傳感器停止工作,MC便選擇優先給2號傳感器充電。

圖4 下一個需要充電傳感器的選擇

圖5 下一個需要充電傳感器的選擇算法

3.4 Tα→i為下一個得到充電傳感器i的最短相遇時間的證明

若已確定傳感器i為下一個得到充電服務的傳感器,在傳感器i的移動路徑上傳感器i和MC有多個可能相遇的位置和對應的相遇時間。而傳感器i與MC的相遇時間Tα→i(Tβ→i)是影響充電策略性能的主要的因素,尤其是對平均充電延遲的影響。若Tα→i(Tβ→i)為最短相遇時間,那么就可以證明此充電策略在充電延遲方面較以往的充電策略有一定的優勢。下面對定理1進行理論證明。

定理1已確定移動傳感器i為下一個得到充電服務的傳感器,在不影響傳感器i執行任務的前提下,傳感器i(1≤i≤n)和MC的最短相遇時間為Tα→i(Tβ→i)。

證明:首先假設移動傳感器i和MC在傳感器i移動T1(0≤T1≤LMS/vs)時間后的位置相遇,而此時MC到達此位置的時間為T′1,路程為S。可由以下公式得到MC路程的表達式:

(10)

(11)

得到T′1的表達式后,可以將問題轉化為不等式的證明問題,比較T1和T′1的大小,得到當且僅當T1=Tα→i時,T1為傳感器i和MC的最短相遇時間。

(12)

(13)

(14)

又因為F(Tα→i)=0 (Tα→i>0)可以得到以下結論:

(0

(15)

(16)

4 仿真實驗

本文中建立了這樣一個仿真環境,建立200 m×200 m的區域,并隨機布置10到100個目標位置和10到100個移動傳感器。我們使用C++實現了本文基于非順序性的最短相遇時間的充電方法NTP(Non-sequence and Shortest Meeting Time Charging Programme)與TBS(The Tree-based Charging Schedule)方法、BCS(The Best-Effort Charging Schedule)方法的對比,在仿真實驗中我們表2列出了所有的默認參數。

表2 仿真參數

4.1 傳感器失效率

傳感器失效率:因能量耗盡而失效的傳感器數目占網絡中所有傳感器總數的百分比。失效傳感器比例是可充電移動傳感器網絡最重要的指標之一,該比例越低說明系統的充電策略越公平高效。

圖6(a)中,隨著充電速度越快,傳感器的失效率越來越低。這是由于隨著充電的速度越快,MC給單個傳感器的充電時間就會越少,充電器可以在一定的時間內為更多的缺電傳感器補充能量,從而降低傳感器的失效率。如圖6(b),隨著傳感器數目增多,系統運行一段時間后,多個缺電傳感器同時提出充電請求,請求充電的傳感器數目也就更多。充電器的能力有限,傳感器失效率隨之變高。如圖6(c),隨著傳感器的速度越快,MC與傳感器相遇的時間變長,單位時間內移動傳感器得到MC充電服務的個數就會越少,導致傳感器失效率越高?？梢钥闯鯪TP算法在降低傳感器失效率方面更加公平。

圖6 不同情況下的傳感器失效率

NTP算法在傳感器失效率方面均比TBS算法和BCS算法更有優勢,這是因為本文考慮了缺電移動傳感器得到充電請求響應公平性問題,使得剩余能量很少,并且其得到能量補充的優先級始終不高的傳感器也能在關鍵時刻得到MC的充電服務,減少了傳感器的失效率。

4.2 平均充電延遲

平均充電延遲:所有提出充電請求的傳感器從發出充電請求到MC與傳感器相遇進行能量補充的時間總和比上總的充電次數。平均充電延遲可以反應系統的響應速度。

圖7(a)中,當充電速度從200增加到400時,每一個缺電傳感器從開始充電到充電完成的時間就越短,MC節省出時間為更多的傳感器提供充電服務。下一個得到充電的傳感器等待的時間越小,平均充電延遲隨之下降。圖7(b)中,由于充電器能力有限,優先度越低的傳感器等待的時間越長,平均充電延遲呈上升趨勢。如圖7(c),當傳感器速度增加時,傳感器失效率升高,提出充電請求的傳感器越少,傳感器等待充電的時間越短,充電延遲越小。

圖7 不同情況下的充電延遲

NTP算法在平均充電延遲方面均比TBS算法和 BCS算法更有優勢,這是因為TBS算法和BCS算法都是按照傳感器提出充電請求的順序進行充電的,會增加MC在充電過程中往復的移動距離,其整體的充電延遲會比較大,并且TBS算法在加權旅行樹中選擇單源最短路徑的過程中會增加MC和傳感器相遇的時間。而NTP算法中,MC與傳感器相遇的時間越短得到充電請求的優先級相對越高,因此MC每次都選擇相遇時間短的傳感器補充能量,減少了MC在充電過程中往復的移動距離,降低充電延遲。

4.3 充電成本

充電成本:MC在給傳感器補充能量的過程中移動的距離總和,即MC與傳感器相遇前移動的距離與相遇后降低速度給傳感器補充能量移動的距離之和。

圖8 不同情況下的充電成本

如圖8(a),充電速度變大充電成本雖然呈下降趨勢,但趨勢并不明顯,這是因為充電過程中MC的移動距離僅僅占充電成本中的一小部分,而決定充電成本的主要因素是MC在和傳感器相遇的過程中移動的距離。圖8(b)中,隨著傳感器數目的增加,在充電器能力范圍內,可以為更多的傳感器補充能量,移動的距離越長其充電成本也越大。但當傳感器的數目大于70時,充電成本的增長率呈下降趨勢,這是因為傳感器數目變多,單位時間內得到能量補充的缺電傳感器數目有限,所以充電成本增長率呈下降趨勢。如圖8(c),隨著傳感器的速度越快,單位時間內移動的距離越長,由于傳感器充滿電所需要的時間都是固定的,因此充電成本越大。

NTP算法在充電成本方面和TBS算法基本持平,但比BCS算法更有優勢。這是因為TBS算法在加權旅行樹中選擇一條單源最短路徑使得整體的充電成本變小,在充電成本方面有很大的優勢。而BCS是按充電請求的順序給傳感器補充能量的,并且沒有綜合考慮充電成本的因素。因此NTP算法比BCS算法在充電成本方面更有優勢。

5 總結

本文探討了一種相遇位置預測的能量補充算法。預測得到MC和傳感器的相遇位置,相遇時間短的傳感器相對相遇時間長的傳感器得到能量補充的優先級相對較高。而后在保證移動傳感器得到充電請求響應公平性的前提下,篩選出能量補充優先級最高的傳感器為下一個充電傳感器。通過大量的仿真實驗對算法進行了分析。實驗結果表明,本文提出的充電方案能夠較好地縮短充電延遲、提高充電效率。