無線傳感器網絡環境下能量有效的虛擬坐標構建

楊 浩

(鹽城師范學院 信息工程學院， 江蘇 鹽城 224002)

1 引 言

無線傳感器網絡(Wireless Sensor Network,WSN)由多個傳感器構成，從而導致數據傳輸路徑多樣化，使得如何準確有效地為構建路由成為一個至關重要的問題[1-3].眾所周知，WSN中的傳感器資源，尤其是能量，是非常有限的.因此，在建立路由的過程中應該盡可能減少傳感器的能量消耗.另一方面，貪婪搜索方式能快速實現數據傳輸.因此，直觀上可以采用貪婪策略來進行無線傳感器網絡的路徑搜索.它的基本思想是網絡中的節點根據地理空間的位置遠近，直接將其鄰居節點作為轉發節點，直至傳輸到sink節點.根據這一方式，僅利用節點的局部信息，就可以建立出節點到終端的路由[4,5].然而，在無線傳感器網絡中，感知單元不穩定性導致網絡中的連接關聯及其不穩定.為此，我們可以利用虛擬坐標系統[6,7]來解決這一問題.具體來說，就是可以將WSN的拓撲圖提取出來，將傳感器作為圖中的節點，相應的通信鏈路作為連接邊，這樣就可以將傳感器轉化為成虛擬坐標.需要注意的是，在轉換過程中要保持對應的保角等價關系.之后，利用貪婪搜索就可以很容易為這些傳感器構建起合適的路由[7].在實際應用中，貪婪搜索方法一般會遇到一個常見的問題—空洞.具體來說，當傳感器在傳輸過程，若其附件沒有可聯通的其他節點時，即存在所謂的空洞現象時.在這種情況下，路徑搜索顯然就會被迫中止，從而導致路由構建的失敗.隨著網絡節點的增加，這一情形顯然很容易發生.空洞問題的出現是由于傳感器物理拓撲關系導致的.

為解決上述問題，本文擬基于雙曲Ricci流構建虛擬坐標.我們基于離散黎曼度量計算三角網格的邊界長度.在這一過程中，為解決實際網絡拓撲可能存在空洞的情形，我們設計一個映射，使得該映射既是保角的又不會陷入空洞.為此，本文用上半盤模型計算雙曲距離，并選擇合適的莫比烏斯變換.利用所得到的虛擬坐標，無線傳感器網絡中的每個節點只需要傳輸所采樣的數據給其鄰居節點，然后利用一般貪婪搜索算法就可以很容易地得到合適的路由.

在實際應用中，將整個網絡進行坐標轉換需要消耗大量能量.為減少轉換過程的能耗，本文進一步提出一個優化方法.它的基本思想是將網絡拓撲進行區域劃分，并構建一個概率性的候選集來選擇合適的待映射節點.實驗證明，我們的優化方法可以在保證有效構建路由的情況下有效地降低轉換能耗.

2 理論背景

本節主要給出相關基本概念，包括黎曼度量、環包度量、高斯曲率和曲面Ricci流等.

2.1 基本概念

2.1.1 黎曼度量

黎曼度量[7]主要用于度量黎曼流形上曲線的長度.假定曲面A在歐拉空間中，則它的第一基本形式(first fundamental form)就是黎曼度量.假設存在兩個正切向量a1=(dx1,dy1),b2=(dx2,dy2)且它們相交于切平面的一個點h∈A，則通過張量度量上述兩個向量的夾角，得

(1)

假定t'是A上的另一個黎曼度量，f(c)是一個方程，若t'=e2f(c)t，則可以認為這兩個黎曼度量是保角的.利用等式(1)，可以得到任意兩個正切向量的角度.實際上，方程f(c)可看作是一個保角因子，用于測量給定區域的變形程度.

需要注意的是，如果曲面M的曲率滿足以下關系：

(2)

其中，?M表示曲面M的邊界，dA表示曲面A的區域，dL表示曲面M的邊界長度，χ(M)<0表示曲面M的歐拉特征數.

2.1.2 環包度量

為了近似擬共形映射問題，Turston提出了環包度量，它可以把度量metric和邊緣相關轉化成metric和vertex 相關[8,9].具體來說，假設存在一個網格空間，每三個頂點組成一個關聯片，且每個頂點連接到一個圓.每個關聯片中，對應的兩個圓是相交的.因此，其邊長顯然就是模型的metric，可以通過圓的相交角計算得出.基于這一方式的度量則稱為環包度量.

根據相關理論，環包度量有共形映射的特性，可以將離散形式的映射以任意精度逼近光滑形式的映射.基于這一性質，可以將環包度量從光滑的曲面擴展至離散的三角網格，從而讓它適用于基于地理拓撲的無線傳感器網絡的路由構建.

2.1.3 高斯曲率[7]

當度量給定后，假設曲面中存在一個三角網格N，其頂點分別為a，b，c，令頂點a的內角為∠a，則a的高斯曲率K為

(3)

其中A表示所有包含點a的三角網格，且當點a邊界處是Λ的值為π，否則為2π.

根據相關理論，對光滑曲面來說，曲率和曲面拓撲之間關系可以用Gauss-Bonner定理來闡述.同時，高斯曲率由黎曼度量決定.

2.2 曲面Ricci流

早在80年代，美國數學家Hamilton就在其黎曼流形中[10]介紹了曲面Ricci流，并在此后的微分幾何發展中，逐漸成為一個熱門研究問題.根據曲面Ricci流相關理論，只要預先給定的曲率變換曲面的黎曼度量，就可以將一個幾何對象通過變換和扭曲實現曲率的相等.

事實上，曲面Ricci流就是基于給定的曲率進行黎曼度量的過程.假定M是一個平滑曲面，且存在黎曼度量g.令t表示時間參數，用g(t)導入高斯曲率K時，則相應的Ricci流可表示為

(4)

當基于曲面Ricci流的方程開始演變后，其高斯曲率將會變得越來越均勻.當達到最終穩定狀態時，即它會流向所需求的目標度量.

3 雙曲Ricci流

為獲得曲面的雙曲拓撲，Chow和Luo等人最先提出了離散Ricci流理論，通過基于metric的參數化方式和簡單的實現方法來處理全局范圍內的共形化，并將參數作為一個整體.然而，在實際的無線傳感器網絡環境的部署中，地理環境是不可預定且可能會隨著時間的推移而發生改變，同時，傳感器的硬件條件限制也可能導致其發生損壞或通信障礙.另外，無線傳輸協議的選擇也在一定程度上影響傳輸拓撲路徑.上述這些情況顯然會使得實際傳輸過程中的拓撲結構圖存在諸如空洞等問題.

為此，我們考慮將節點的映射空間變換到雙曲空間.基于這一分析，本節首先闡述曲面Ricci流擴展到雙曲Ricci流的相關概念.

3.1 離散的黎曼度量

對于一個給定的網格，離散的黎曼度量將方程F

(5)

變成為方程G

G:H→R+

(6)

這意味著，對于該網格中的一個三角面來說，若三條邊界長度滿足兩邊之和大于第三邊，則對應的夾角滿足雙曲余弦定理.

3.2 雙曲Ricci流

給定一個逆距離環包度量，則雙曲Ricci流為

(7)

4 基于雙曲Ricci流的虛擬坐標構建

對一般傳統的Ricci流來說，曲面中包含的三角網格中對應每個頂點夾角必須小于90度.這是因為，當曲面網格中的向量夾角不是銳角時，離散Ricci流會出現不穩定的情形，從而無法得到全局最優解，甚至出現無解的情況.然而，對實際環境下的無線傳感器網絡來說，所部署的物理空間是不確定的，且傳感器本身造成的失效等因素也會導致拓撲關系的改變.換句話說，實際環境下的網絡拓撲很難滿足這一要求的約束.

為解決這一問題，本文采用了雙曲Ricci流進行環包度量[11].在計算度量過程中，我們采用上半盤表示雙曲空間.其中，雙曲空間的距離的計算方法使用了并使用了交叉比率絕對值的對數的方式.同時，我們選擇了合適的莫比烏斯變換.為減少映射過程的能耗，我們進一步基于候選集的思想提出了優化方法，以減少迭代次數.最后，給出相應的虛擬坐標構建算法.

4.1 基于雙曲Ricci流的環包度量

根據上文所述，真實環境下的無線傳感器網絡拓撲中的有可能存在節點的向量夾角大于90度，這將導致該節點無法把信息傳遞給更靠近目的地的后繼節點.因此，在這種情況下，利用貪婪路由策略不能成功地獲得合適的路由.為此，文獻[11]將傳統的環包度量變為雙曲空間中的逆距離環包度量，即

lij=cosh-1(coshricoshrj+Iijsinhrisinhrj)

(8)

其中，Iij表示逆距離，ri和rj是兩個環的半徑.

4.2 雙曲空間上半盤模型

(9)

其中，雙曲空間的距離的計算方法為交叉比率絕對值的對數.

本文利用的莫比烏斯變換為

(10)

其中，a,b,c,d均為實數，且滿足ad-bc=1.

4.3 候選集構建

顯然，將整個網絡進行坐標映射需要耗費傳感器的大量能量.因此，本文考慮將網絡拓撲進行分區，然后選擇部分傳感器作為映射候選集.在區域內采用貪婪算法進行路由構建，區域間的路由構建則從候選集中選擇合適的節點.分區的方式根據實際情況的需要進行預先分配.

本文主要關注的是候選集的建立.具體來說，候選集構建過程是：令區域Ci的候選集為Vi，邊界為Bi.若va到達Bi的跳數不超過2，則生成一個概率性并基于這一概率將該點并入候選集.其中，概率的選擇主要由實際分區內的地理拓撲位置及其具體的通信鏈路狀態決定.一般來說，選擇方式有固定和變化兩種情形.本文的實驗部分將會對比這兩種方式的效果.對每個子區域來說，當它們都構建候選集后，將整個網絡的候選集合并.顯然，該方式充分考慮了邊緣節點及其臨近節點的在路由構建中的作用，因此使得所構建的路由是全局最優的.換句話說，利用候選集的方式來構建拓撲則避免了將全部網絡都進行虛擬映射的過程，從而極大地節約了傳感器的能量消耗.

我們將在下一節的實驗中將上述優化方式與不使用候選集的方法進行對比.實驗結果顯示，使用候選集可以有效降低映射過程的能耗.

4.4 構建虛擬坐標的算法

雖然保角變換改變環半徑，但卻不改變逆距離，因此進行這種變換僅需要計算邊界長度.根據這一性質，我們將網絡拓撲中所有滿足三角不等式形式的節點映射為虛擬坐標，具體算法如下：

算法： 為無線傳感器網絡節點構建對應的虛擬坐標輸入：根據實際部署的物理環境，給定相應的三角網格，其中可能存在空洞現象輸出：所有傳感器映射的虛擬坐標1． 將整個網絡拓撲按照預定要求進行分區2． 對每個區域使用選擇概率獲得對應的候選集．其中，選擇概率根據實際分區中的傳感器部署情況決定3． 計算最長邊界的長度，并利用傳感器通信半徑進行約束4． 選擇三個節點將之嵌入到平面5． 對于其中的非映射點，檢查其鄰居平面．若其鄰居被映射，則將該平面嵌入曲面．6． 令該映射點到源點的距離在最長邊界的長度的1．8～2．1倍之間，令其為上半盤的中心，并將其坐標映射為相應的虛擬坐標．

需要注意的是，在實際應用中，對虛擬坐標的構建要考慮傳感器的通信半徑，這一點至關重要.另一方面，根據實驗驗證，映射點到源點的距離并不是固定選取最長邊界的長度的兩倍，而是應該在一定的范圍，原因是隨著無線傳感器網絡中通信要求的改變及其所使用的通信協議，傳感器的通信半徑會發生相應的調整，從而使得最長邊界的長度的約束條件發生改變.因此，不使用固定范圍的方式是符合實際情況的.

5 實 驗

本節驗證了所設計算法的有效性.為更好地檢驗其性能，我們充分對比了傳統Ricci流方法.進一步，我們檢測了優化方法的效用.

5.1 對比傳統方法

本文首先對比了傳統Ricci流方法.在實驗中，我們首先將節點分成四組，每組數量分別為10個、30個、50個和90個.它們都是以自組織方式收集一次信息.為保證對比實驗的準確性，算法執行100次，然后取結果的平均值.根據實驗結果圖1所示，本文提出的算法在虛擬映射過程中所需的迭代次數比傳統方法少.更重要的是，當網絡規模增大時，迭代次數增加非常有限，原因是迭代次數的增加與節點數的增加的比率變化較小.顯然，這一優勢使得隨著網絡節點數目的增加，映射能耗需求變化平穩，因此本文方法適用于大規模傳感器網絡.

無線傳感器網絡的能量有限特性使得映射過程的迭代次數無法無限制的增加.這意味著即使網絡規模不斷增加，也要限制其迭代次數.在這種情形下，路由可能無法被有效構建.為此，本文進一步驗證路由構建的成功率與迭代次數的關系.我們的實驗采用的是90個傳感器的網絡，且迭代次數分別設為20次、50次、100次和150次.如圖 2(b)所示，在相同的迭代次數下，本文算法的成功率較高.因此，該算法可以在迭代次數受限的情況下，盡可能為無線傳感器網絡成功構建合適的路由.

5.2 評估優化方法

本節評估了所提出的優化方法在不同網絡規模下的迭代次數和能量消耗.其中，網絡中的傳感器個數與上節實驗相同.

圖3展示了本文優化方法所需的迭代次數與網絡規模的關系.其中，優化方法的選擇概率分別規定為固定概率和變化概率.根據實驗結果，我們的優化方法可以成功構建路由且所需迭代次數小于傳統方法，并且當網絡規模增大時，能耗節約更大.另外，與上節相似，優化方法所需的迭代次數的增加與節點數的增加的比率增加相對緩慢，因此適合在大規模傳感網網絡環境下使用. 另一方面，當選擇概率變化時，其迭代次

圖1 節點數和迭代數的關系Fig.1 Relationship between the number of both nodes and iterations

圖2 迭代數和成功率的關系Fig.2 Relationship between the number of iterations and the successful rate

圖3 優化方法與傳統方法對比Fig.3 Comparison of the optimal schemes and traditional scheme

數總體上少于選擇概率固定時的迭代次數，這是因為隨著傳感器網絡的傳輸，部分節點的鏈路通信質量發生變化，從而導致網絡的拓撲結構發生改變.因此，變化的選擇概率更加適應這一情形.從映射結果上來看，優化方法可以達到全局最優.這意味著不選將整個網絡中的傳感器進行虛擬映射，極大地節約了節點的能耗.

上述實驗說明優化方法在保證路由構建正確的前提下，具有明顯的能耗優勢，可以用于實際無線傳感器網絡中的路由建立及其數據傳輸.

6 結 論

為了快速準確地構建合適的無線傳感器網絡路由，本文提出了一種虛擬坐標構建方法并利用貪婪搜索方式進行路由建立.該方法針對貪婪策略無法解決的空洞問題，利用保角映射方法將網絡中的節點映射為相應的虛擬坐標，隨后通過直接轉發的方式即可得到合適的路由.為降低映射過程能量消耗，本文進一步設計利用候選集來減少不必要的迭代次數.候選集的標準為區域內距離邊界不超過兩跳的節點.實驗驗證了本文的方法由于傳統的Ricci流方法，且所設計的優化方法也極大地降低了網絡能耗，并適用于大規模傳感器網絡.

[1] Naranjo P G V,Shojafar M,Abraham A,et al.A new s
Table election-based routing algorithm to preserve aliveness and energy in fog-supported wireless sensor networks[J].Proceedings of the IEEE Systems,Man,and Cybernetics,2016:1-6.

[2] Sharma A,Agrawal M,Sondhi M,et al.Analysis and simulation of energy efficient optimal scenarios for cluster based routing protocol in wireless sensor network[J].Journal of Network Security Computer Networks,2016,2(1):79-86.

[3] Rahat A A M,Everson R M,Fieldsend J E.Evolutionary multi-path routing for network lifetime and robustness in wireless sensor networks[J].Ad Hoc Networks,2016,52:130-145.

[4] Liu J,Wan J,Wang Q,et al.A survey on position-based routing for vehicular ad hoc networks[J].Telecommunication Systems,2016,62(1):15-30.

[5] de Oliveira H A B F,Boukerche A,Guidoni D L,et al.An enhanced location-free greedy forward algorithm with hole bypass capability in wireless sensor networks[J].Journal of Parallel and Distributed Computing,2015,77:1-10.

[6] Das D,Misra R,Raj A.Approximating geographic routing using coverage tree heuristics for wireless network[J].Wireless Networks,2015,21(4):1109-1118.

[7] Tromba A.Teichmüller theory in riemannian geometry[M].Birkh?user,2012.

[8] Stephenson K.Introduction to circle packing:The theory of discrete analytic functions[M].Cambridge University Press,2005.

[9] Thurston W P,Milnor J W.The geometry and topology of three-manifolds[M].Princeton:Princeton University,1979.

[10] Hamilton R S.The Ricci flow on surfaces[J].Contemporary Mathematics,1988,71(1):237-261.

[11] Yang Y L, Guo R, Luo F,et al. Generalized discrete Ricci flow[J]. Comput. Graph. Forum, 2009,28(7): 2005-2014.

[12] Chow B, Luo F. Combinatorial ricci flows on surfaces[J]. Communications in Contemporary Mathematics, 2012, 63(1):765-780.

[13] Terras A. The poincaré upper half-plane[M]. Springer New York, 2013.