多跳無線可充電傳感器網絡中諧振中繼器部署方法*

吳 淵， 馮 勇， 郭 磊， 楊 心

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

0 引 言

無線傳感器網絡中節點受成本、體積等因素的限制，為其配置的電池容量有限[1，2]，能量問題是限制無線傳感器網絡生存周期和性能的最主要因素。當前發展的無線充電技術被普遍認為是突破無線傳感器網絡能量限制的最具前景的技術，無線可充電傳感器網絡(wireless rechargeable sensor networks,WRSN)應運而生，許多卓有成效的方案[3,4]被提出。根據所采用無線充電技術的不同，WRSN能量補充方案可以分為單對單和單對多充電兩種類型。單對單充電方案簡單靈活，但是一次只能給一個節點充電，存在著充電效率不高、充電距離受限等方面的問題。單對多充電方案[5,6]可以同時給網絡中多個節點充電，且利用諧振中繼器可以實現多跳充電，可顯著延伸充電距離、提高網絡的能量補充效率。目前的WRSN單對多充電方案[9～11]中,每個傳感器節點上都配備一個諧振中繼器，利用移動充電裝置(mobile charger,MC)移動到合適的位置(即錨點)以單跳或多跳方式同時給多個傳感器節點補充能量。

文獻[7]利用相鄰的正六邊形單元格平等分割網絡，傳感器節點被覆蓋在單元格內，MC周期性移動到單元格中心位置來實現能量的多跳無線傳輸。文獻[8]提出了一

種多跳充電模型，證明能量中繼4～5跳可以實現50 %以上的充電效率。文獻[9]提出了能量可以同時傳輸給多個充電請求節點，證明了MC給多個節點充電的總輸出效率比給單個節點充電的總輸出效率更高。文獻[10]針對節點的稀疏部署和密集部署分別提出了不同的解決方案。節點稀疏部署的方案是利用虛擬節點作為無線能量路由器，運用多跳無線充電方式來提高能量的傳輸效率。在節點密集部署的方案中，傳感器節點以瞄準線的方式實現能量的多跳傳輸。

以上多跳能量補充方法都是以傳感器節點作為中繼器，受節點部署密度以及MC有效充電距離的限制，網絡中能夠滿足多跳能量傳輸的節點較為有限[11]，這在一定程度上影響了能量補充效率。為了改善以上問題同時兼顧經濟性，本文提出了如何以最少的諧振中繼器實現對WRSN中節點的完全多跳充電覆蓋這一問題。在此基礎上，給出了一種包括兩個步驟的諧振中繼器位置確定策略(repeaters location determination strategy,TRLDS)。首先使用蜂窩六邊形分割網絡以保證網絡中節點的完全多跳充電覆蓋，其次設計了一組規則以減少中繼器數量并優化中繼器位置，以實現用盡可能少的中繼器對網絡中所有節點的完全多跳充電覆蓋，進而有效改善網絡能量補充效率這一目標。

1 網絡模型與問題定義

1.1 網絡模型

本文將傳感器節點(sensor node,SN)隨機分布于二維平面區域中，傳感器節點的數目為N，每個節點初始能量為Emax，能量閾值標記為Emin。如圖1，整個網絡由四種類型的成員組成：諧振中繼器節點(repeater node,RN)，固定的基站(base station,BS)， MC，傳感器節點構成。假設MC裝有大容量電池和無線能量發送裝置與接收裝置，且具有智能通信、計算和移動的能力。MC可以在BS處通過休眠狀態補充自身電量。

圖1 網絡模型

1.2 充電覆蓋定義

假設1WRSN區域V=a×b，a，b為區域的邊界大小；傳感器節點集合定義為S={Si│0≤i

假設2所有諧振中繼器節點集合定義為R={Rk│0≤k

假設3Rj的充電覆蓋半徑為L，傳感器節點Si被Sj或中繼節點Rk充電覆蓋的概率為

(1)

式中Si為網絡區域中第i個傳感器節點；Um=Rk∪Sj，Rk為第k個中繼器節點，Sj為第j個傳感器節點，j≠i,d(Um,Si)為Si與Rk或Sj之間的距離。

傳感器節點Si被多個中繼節點聯合覆蓋的概率為ρ(R′,Si)=1-∏(1-ρ(Rk,Si))，R′={Rn-k,Rn-k+1,…,Rn-1,Rn}，R′?R。傳感器節點Si被多個中繼節點聯合覆蓋時，Si屬于Rk的充電覆蓋下的概率為

(2)

式中mark(i)為節點Si被中繼節點Rk覆蓋的標記。

完全多跳充電覆蓋定義在給定的WRSN中，??Si,Sj∈H，Rk,Rc∈R′，Um=Rk∪Sj。均?ρ(Um,Si)=1或ρi(R′,Si)=1,ρJt(Rk,Si)=1恒成立，則稱WRSN是完全多跳充電覆蓋網絡。

多跳充電覆蓋率定義在WRSN中，?H′={Si,Si+1,…,St}，H′?H。??Sj∈H且Sj?H′，Rk∈Z，其中i,j∈N，Um=Rk∪Sj,?ρ(Um,Si)=1，ρJt(Rk,Si)=1成立，則t-i+2與N的比值稱為多跳充電覆蓋率。

2 諧振中繼器位置的確定

2.1 諧振中繼器均勻部署

為了在網絡中均勻部署RN，需要研究網絡中SN之間的連通性。假設RN的最大充電半徑為R，網絡中無線鏈路的邊可以表示為Γ=(U,Z),U=H∪Z，Γ為傳感器網絡圖，U為網絡中節點的個數，H為傳感器節點集合，Z為中繼器節點集合。

網絡中的邊Eij滿足以下條件

(3)

網絡的連通性[12]為

(4)

基于網絡的連通性，利用蜂窩六邊形和兩個SN的中點確定方法來分割網絡。通過將RN均勻部署于正六邊形的中心位置上，一方面考慮部署的公平性，另一方面考慮傳感器網絡的完全覆蓋。

為了使RN在網絡中合理部署，本文給出確定RN位置的證明。在WRSN中，為了計算網絡中任意相鄰的正六邊形的中點坐標，假設存在任意相鄰的3個正六邊形，如圖2所示，3個中點分別為R1=(x1,y1),R2=(x2,y2),R3=(x3,y3)。滿足R1,R2,R3∈S，已知節點R2=(x2,y2)，目標是求解中繼節點R1,R2的坐標。連接3個頂點可以得到3條邊分別為d1,d2,d3∈E，A為3個正六邊形的交點，過點R1畫邊d2的垂線交于點E，連接AR3。

圖2 相鄰正六邊形RN確定

(5)

通過使用相鄰蜂窩六邊形來分割網絡部署RN時，RN的數量較多，增加了網絡的物理成本。該方案中存在RN覆蓋一個或兩個SN的情況，相對RN增加了部署成本的問題。由式(4)得，網絡的連通性是確定RN位置的依據，同時決定著RN充電覆蓋SN的數量。針對上述問題，本文假設在WRSN中，存在任意兩個傳感器節點S1和S2，當S1,S2之間的距離d∈[λ,2R](λ為S1,S2距離的閾值)時，由文獻[13]，將原先覆蓋S1,S2的RN部署在S1,S2的中間位置。該策略可以增加網絡的連通性，提高RN的整體充電覆蓋率，降低RN的部署成本。

2.2 諧振中繼器具體部署過程

在WRSN中，多跳充電效率隨著充電距離的增大而衰減，因此多跳充電的距離和跳數是有限的。通過部署RN可降低多跳充電的跳數，延長充電距離，實現網絡的充電全覆蓋。為了詳細地闡述RN的部署過程，給出RN部署規則：

規則一根據多跳充電的有效距離，使用蜂窩單元格分割網絡時，將RN部署于相鄰單元格的中心位置。

規則二當單元格中僅充電覆蓋兩個傳感器節點且兩節點之間的距離在[λ,2R]范圍內，由文獻[13]，規定將RN位置調整于兩個SN的中點位置。

規則三當中繼節點Ri僅充電覆蓋一個傳感器節點Si時，若Si在相鄰中繼節點Rk的充電覆蓋范圍則重新標記該SN的mark值并刪除冗余中繼節點Ri。

規則四當中繼節點Ri僅充電覆蓋一個傳感器節點Si時，若Si與相鄰中繼節點Rk覆蓋的其他傳感器節點之間的距離d均小于2R(R為RN的充電覆蓋半徑)，則重新部署Rk于d最大的兩個傳感器節點的中點位置并刪除冗余的中繼節點Ri。

規則五當RN充電覆蓋一個SN時，任意兩個單元格中SN之間的距離小于2R，則部署其中一個RN于這兩個SN的中點位置并刪除另一個單元格的中繼節點。

規則六當中繼節點Ri僅充電覆蓋一個傳感器節點Si時，若Si到相鄰中繼節點Rk覆蓋的傳感器節點Sj(距離Si最近)之間距離小于2R，則調整Ri的位置與Si,Sj的中點位置。

根據上述規則，結合圖3給出以下具體RN部署方案。

圖3 諧振中繼器位置確定

1)判斷所有tab=2的RN，根據規則二來調整RN位置。RN調整后的位置如圖中五角星點的位置。

2)判斷所有tab=1的RN位置，確定距離平面坐標原點最近的Ri(tab=1)。根據規則三來刪除冗余的RN并將傳感器節點重新標記(圖中空心點位置)，否則判斷是否滿足規則四的調整方案,若是,則依規則四來調整RN位置，反之,依據規則五按照圖中所示進行調整RN，若上述調整方案均不能解決RN覆蓋一個節點的問題，則根據規則六來調整RN位置。若上述規則均不滿足,則對RN的位置不進行任何處理。圖3(e)中的RN位置由五角星點和三角形點組成。圖3(f)中每個傳感器節點都被標記過，空心圓為調整的傳感器節點。星點為RN調整之后的位置。圖中虛線為多跳充電覆蓋連接線。

3 仿真與性能評估

本文通過仿真對比TRLDS與Cellular[7]來說明本文所提方案的有效性。本文主要工作是諧振中繼器的位置部署以及優化工作，因此從以下指標評估本文所提方法的有效性。默認的仿真參數為：仿真區域為30 m ×30 m，傳感器節點數量N為[25,200]，節點的初始能量E為10 000 units，工作狀態的能耗Ew為10 units/s，休眠狀態的能耗Es為1 unit/s，傳感器范圍為3 m，MC移動速度為3 m/s，目標節點速度1～ 5 m/s，仿真時間36 000 s，充電速率200 units/s。

3.1 多跳充電覆蓋率

根據定義可知，若ρ(Um,S)=1成立，那么RN覆蓋的節點數量是不同的。如圖4(a)表示RN在數量不同下的多跳充電覆蓋率的變化情況。當RN的充電覆蓋半徑為2 m時，可以看出RN數量在0～14之間變化，多跳充電覆蓋率呈遞增趨勢。當RN數量為11時，TRLDS的多跳充電覆蓋率達到1，而Cellular的多跳充電覆蓋率為0.62。因此，在RN數量一定條件下，TRLDS的多跳充電覆蓋率更高。如圖4(b)表示RN不同充電覆蓋范圍下的多跳充電覆蓋率的變化情況。當RN數量為8時，可以看出隨著RN充電覆蓋范圍的變大，多跳充電覆蓋率相繼增大。在相同的條件下，可明顯看出TRLDS的多跳充電覆蓋率更高。

圖4 不同條件下多跳充電覆蓋率的性能對比

3.2 充電性能評估

在WRSN中部署RN條件下，圖5(a)中充電成本表示MC為實現節點能量補充的總移動距離。從圖中看出當節點數量小于125時，充電成本呈遞增趨勢，節點數量大于125時，充電成本呈遞減趨勢，這是因為隨著節點數量的增多，節點死亡率變大，MC來不及給網絡中請求充電節點充電導致移動成本降低。從圖中可以看出TRLDS的充電成本更小。圖5(b)中網絡生存時間表示無線可充電傳感器網絡從開始運行到停止運行的時間間隔。從圖中看出節點數量從25增加到200時，網絡的生存時間呈遞減趨勢，這是因為隨著節點數量的增多，MC來不及給目標節點充電而導致網絡停止。通過對比說明，TRLDS在充電性能方面具有明顯優勢。

圖5 布置算法在不同條件下的充電性能對比

4 結 論

本文探討了在WRSN中合理部署諧振中繼器以提高網絡的充電效率問題。由于多跳無線充電效率受網絡中RN位置和數量的影響，本文研究了RN部署問題，提出了一種包括兩個步驟的RN位置確定策略—TRLDS，顯著地延伸了移動充電裝置的充電距離，從整體上提高充電效率。仿真結果表明該策略能夠以一種較低成本的方式有效解決無線傳感器網絡中節點的能量受限問題，實現網絡的可持續性運行。