一種基于轉發區域的三維地理位置路由協議

陳聰 冀肖榆 農健

摘 要： 在真實的無線傳感網絡（WSNs）應用環境中，傳感節點位于三維空間。為此，提出基于錐形轉發區域的三維地理位置路由協議。為了減少冗余數據包數、降低數據包碰撞概率，CFRG協議先建立錐形轉發區域，其目的在于限制轉發節點數。然后，再估計錐形轉發區域內節點的轉發概率，最終選擇具有最大轉發概率的節點轉發數據包。當節點遭遇空洞節點問題，就自適應地調整錐形轉發區域體積，擴大選擇轉發節點的空間，即通過錐形轉發區域調整，解決VNP問題。仿真結果表明，提出的CFRG協議能夠處理VNP問題。與同類的三維路由協議相比，CFRG協議能夠提升端到端傳輸時延和數據包丟失率兩方面性能。

關鍵詞： 無線傳感網絡; 地理位置路由; 三維路由協議; 錐形轉發區域; 空洞節點問題; 傳輸時延

中圖分類號： TN915.04?34; TP393 文獻標識碼： A 文章編號： 1004?373X（2018）09?0035?06

Abstract： In the actual application environment of wireless sensor networks （WSNs）， the sensor nodes are located in three?dimensional space. Therefore， the conical forwarding region?based 3D geographical （CFRG） routing protocol is proposed. In order to decrease the redundant data packets and reduce the collision probability of data packets， the conical forwarding region is constructed for the restriction of the forwarding node numbers. The forwarding probabilities of the nodes in the conical forwarding region are estimated to select the node forwarding data packet with the maximum forwarding probability. When the node experiences a void node problem （VNP）， the volume of the conical forwarding region is adjusted adaptively for enlarging the space of forwarding node selection to solve the VNP. The simulation results show that the proposed protocol can resolve the VNP， and reduce the end?to?end transmission delay and data packet loss ratio in comparison with the similar 3D routing protocols.

Keywords： wireless sensor network; geographical routing; three?dimensional routing protocol; conical forwarding region; void node problem; transmission delay

0 引 言

隨著傳感技術的迅速發展，無線傳感網絡（Wireless Sensor Networks，WSNs）得到廣泛應用[1?3]。通過部署WSNs傳感節點先收集環境數據，再傳輸至基站，最后通過Internet網絡將數據傳輸至后臺管理人員，進而實現實時監控環境的目的。這些應用均要求實時、可靠地傳輸數據包[4]。地理位置路由（Geographical Routing Protocols，GRPs）無需維護路由和發現路由階段，因此，相比于拓撲路由協議，GRPs能夠提供可靠、實時的數據包傳輸服務[5?6]。

在真實的WSNs環境中，傳感節點部署于三維（3D）空間，如海洋監測[7?8]、森林火災感測[9]。針對這些應用，GRPs必須利用三維位置坐標。而二維的GRPs只是利用平面路由技術選擇路由，與真實的三維空間不符。文獻[10?12]的實驗結果表明，三維GRPs能夠提高數據包傳遞的可靠性。

此外，GRPs的關鍵在于給節點提供位置信息。而利用GPS系統能夠獲取節點的三維信息[13]。GRPs的另一個問題在于空洞節點問題（Void Node Problem，VNP）。所謂VNP就是在發送節點方向上沒有轉發節點。二維GRPs通常采用平面路由技術處理VNP問題，然而，這些技術不能應用于三維GRPs中。

為此，本文提出基于錐形轉發區域的三維地理位置路由（Conical Forwarding Region?based Geographical，CFRG）協議。CFRG協議通過建立錐形轉發區域控制數據包的冗余，并計算轉發概率，選擇最大概率的節點傳輸數據包。同時，CFRG路由利用實時調整錐形轉發區域，使其包含更多的節點，提升選擇轉發節點的選擇空間。實驗數據表明，提出的CFRG路由協議能降低數據包傳輸時延和數據包丟失率，也能有效地處理VNP問題。

1 約束條件及CFRG路由概述

1.1 約束條件

假定無線傳感網絡內有[N]個同構節點，且隨機分布于興趣區域內。這些節點是靜態的，每個節點的傳輸距離為[r ]m。[N]個同構節點所形成的三維體積為[V]。

此外，假定網絡內所有節點均知道目的節點、源節點的位置。這些信息均載入在數據包的首部中。在多數WSN中，目的節點（基站）均部署在預定位置，因此目的節點位置可認為是已知的。

1.2 CFRG路由概述

CFRG路由目的在于提高數據傳輸效率，減少傳輸時延。CFRG路由先構建錐形轉發區域，進而控制轉發數據包的節點數，降低擁塞。同時，通過估算轉發區域內每個節點轉發數據包的概率，擇優選擇概率最大的節點作為轉發節點，減少數據包的傳輸時延。

此外，CFRG路由的另一個特點在于解決了三維VNP問題，這也是GRPs的共性問題。CFRG路由通過實時調整錐形轉發區域，解決VNP問題。

2 CFRG路由

2.1 錐形轉發區域PFR

首先定義數據包轉發區域，即錐形轉發區域。該區域內節點被認為是潛在的轉發節點。為了減少傳輸次數，錐形轉發區域應盡可能地小。即希望錐形轉發區域內只含有一個最理想的轉發節點。從另一種角度而言，錐形轉發區域應當足夠大，即盡可能提高區域內包含最理想的轉發節點概率。

當源節點[S]需要發送數據包時，先建立錐形轉發區域。最初，為了減少傳輸次數，盡可能地減少錐形轉發區域，使其含有足夠少，但存在合適的轉發節點。為此，錐形轉發角[β]反比于網絡密度[ρ=NV]。網絡密度越大，錐形轉發區域越小，反之，越大。據此，初始的錐形轉發角[βinit]為：

2.2 轉發節點集

當接收來自源節點或發送節點[S]發送的數據包，接收節點就需要判斷自己是否在錐形轉發區域內。若在區域內，就可成為候選轉發節點，即納入轉發節點集[ψ]內。

假定節點[S]的位置坐標為[Sx，Sy，Sz]。節點[S]所發送的數據包的首部包含其位置坐標信息。任何節點（假定為節點[ni]）接收了該數據包，節點[ni]就確認自己是否在錐形轉發區域內。

假定節點[ni]和目的節點[D]的位置坐標分別為[nx，ny，nz，][Dx，Dy，Dz]。先計算兩個矢量[SD→]與[Sn→]的夾角[θ]：

式中[β]為錐形轉發角。如果滿足，則說明該節點在錐形轉發區域內，并納入候選轉發集[ψ]（[ψ←ni]），成為潛在轉發節點;否則，將該數據包納入空洞節點數據包清單Void_node_packetlist，便于后續處理。

當然，最初所有節點均按式（3）判斷是否在錐形轉發區域。如果發送節點在發送數據包后，經一段時間后，節點仍沒有監聽到數據包被轉發，說明該數據包沒有被節點接收。因此，源節點或發送節點就重傳該數據包，并調整轉發角[β]，具體過程見2.4節。

2.3 轉發概率

2.3.1 時 延

當錐形轉發區域內有多個節點時，就需要計算每個節點的轉發概率，主要通過時延估計計算轉發概率。

先計算錐形轉發區域內每個節點將數據包傳輸至目的節點所需要的時間，即估計傳輸時延[τreq。][τreq]主要取決于兩個因素：轉發節點[ni]和目的節點[D]間的跳數[h];每跳的時延[τh]。

對于跳數[h]可通過[SD→r]決定。而每跳的時延[τh]由多個因素決定：

2.3.2 適度性

如果節點位于錐形轉發區域，并發現自己能夠在數據包有效期[Tthreshold]前傳遞數據包，那么該節點就可成為潛在轉發節點。如果錐形轉發區域中有多個節點時，就進一步分析這些節點中哪個節點更適合傳輸數據包，即節點傳輸數據包的“適度性”。

可利用潛在轉發節點的隊列時延以及它之前傳輸[m]個數據包的平均傳輸時延[τav]估算節點的“適度性”。由源節點計算時延[τav，]如式（6）所示：

2.4 VNP處理

在GRPs路由中，節點可能遭遇路由空洞問題，這也是GRPs路由的共性問題。CFRG主要通過自適應調整轉發區域體積，即調整[β]角處理VNP問題。

錐形轉發區域調整機制如圖2所示。若基于初始[βinit]角建立的轉發區域[PFR1]內沒有轉發節點，就意味著遭遇VNP。因此，一旦轉發節點[S]遭遇VNP，就需要重新建立錐形轉發區域。轉發節點[S]發送了數據包后，經時期[τω]后，若沒有監測到鄰居節點重傳數據包，說明它（轉發節點[S]）遭遇VNP問題。在這種情況下，轉發節點[S]就重傳數據包。此外，時間[τω]可依據文獻[14]調整。

位于初始錐形轉發區域外的節點，通過確認Void_node_packetlist內數據包ID號。若數據包在它的Void_node_packetlist內，就將[β]擴大1倍，即將錐形轉發區域擴大，使其包含更多潛在轉發節點。將這一過程稱為錐形轉發區域調整過程。

如圖2所示，其描述了錐形轉發區域調整機制。最初，源節點[S]通過[PFR1]區域轉發數據包，后發現[PFR1]區域內沒有轉發節點;然后調整[β]形成了[PFR2]區域，再試圖轉發數據包，仍發現[PFR2]區域內沒有轉發節點，無法將數據包傳遞至目的節點[D]。至此，再次調整[β]形成[PFR3]區域。最后，發現[PFR3]區域內有節點[n1]，且其能夠將數據包傳輸至目的節點。盡管節點[n1]不是通過最短路徑向目的節點[D]傳輸數據包，但是它能夠解決VNP問題。

3 數值分析

3.1 仿真場景

利用OMNeT++[15]仿真軟件建立仿真平臺。仿真運行時間為5 min，且每個數據包的截止時長為250 ms。具體仿真參數如表1所示。

此外，為了更好地評估CFRG協議性能，選擇ABLAR和3D 貪婪（Greedy）路由作為參考。前者利用隨機轉發技術解決3D VNP問題，而后者是典型的GRPs策略，并利用平面路由技術解決3D VNP問題。這兩者與CFRG協議存在可比性。

在分析CFRG協議性能時，選擇端到端傳輸時延和數據包丟失率作為性能指標。每次實驗獨立重復10次，取平均值作為最終的仿真數據，最終的仿真數據如圖4～圖7所示。

3.2 CFRG協議性能

單獨分析CFRG協議性能時，主要分析其端到端傳輸時延、數據包丟失率隨錐形轉發角[β]的變化情況， 且[β]從0～360°間變化，仿真結果如圖4，圖5所示。

圖4描述了端到端傳輸時延隨[β]的變化曲線。從圖4可知，在網絡密集區域，[β]越大，端到端傳輸時延也就越大，原因在于密集區域，一旦[β]增加，意味著更多的節點需要轉發數據包，加劇網絡擁塞，最終提升了端到端傳輸時延。

圖5繪制了數據包丟失率隨錐形轉發角[β]的變化曲線。從圖5可知，在網絡負擔（12 packets/s）大的環境下，錐形轉發角[β]對數據包丟失率有重要的影響。原因在于網絡負擔越大，節點需要傳輸更多的數據包，這也會造成數據包傳輸擁塞，甚至數據包碰撞，便增加了數據包丟失率。這些數據表明，依據網絡密度選擇合適的[β]是非常重要的。

3.3 對比分析

本小節主要分析網絡流量對端到端傳輸時延、數據包丟失率的影響，其中網絡流量用源節點每秒產生的數據包數表征。假定網絡內有1 000個節點，4個源節點，源節點每秒產生數據包數從1～14變化。

3.3.1 端到端傳輸時延

首先，分析端到端傳輸時延隨網絡流量變化情況，如圖6所示。

從圖6可知，與3D Greedy和ABLAR相比，提出的CFRG協議的端到端傳輸時延最低，并且隨網絡流量變化波動小。這主要是因為CFRG協議在決策轉發數據包時，考慮了轉發擁塞問題，并將時延信息融入了轉發概率，這有利于降低擁塞概率。

3.3.2 數據包丟失率

數據包丟失率是反映路由協議性能的重要指標。三個協議的數據包丟失率隨網絡流量的變化曲線如圖7所示。從圖7可知，三個協議的數據包丟失率隨網絡流量的增加而上升。而與ABLAR協議和3D Greedy 協議相比，CFRG協議的數據包丟失率最低，特別是在低網絡流量情況下，CFRG協議在數據包丟失率方面的優勢特別明顯。例如，在低網絡流量時，即當數據包產生率不大于6 packets/s，CFRG協議的平均數據包丟失率約為8%，而3D Greedy協議、ABLAR協議分別高達32%，44%。

然而，當數據包產生率大于6 packets/s后，CFRG協議的數據包丟失率急劇增加。盡管如此，CFRG協議的數據包丟失率仍遠優于ABLAR和3D Greedy協議。這主要歸功于CFRG協議能夠實時調整、擴大轉發區域，增加了選擇轉發節點的空間，進而有利于處理VNP問題。

4 結 語

本文針對無線傳感網絡的路由問題，提出基于錐形轉發區域的三維地理位置路由協議CFRG。CFRG路由充分考慮了節點位置的三維空間特性，通過網絡密度構建錐形轉發區域。只有錐形轉發區域內的節點才能轉發數據包，通過這種方式控制轉發數據包的數量，降低數據包碰撞概率。一旦節點遭遇VNP問題，就調整錐形轉發區域。最終，通過計算錐形轉發區域內每個節點的轉發概率，擇優選擇轉發節點傳輸數據包。仿真結果表明，提出的CFRG路由能夠有效處理VNP問題。與同類的3D地理位置路由相比，CFRG路由降低了數據包傳遞時延，并提高了數據包傳輸成功率。

參考文獻

[1] YICK J， MUKHERJEE B， GHOSAL D. Wireless sensor network survey [J]. Computer networks， 2008， 52（12）： 2292?2330.

[2] AKYILDIZ I F， SU W， SANKARASUBRAMANIAM Y， et al. A survey on sensor networks [J]. IEEE communications magazine， 2002， 40（8）： 102?114.

[3] DIETRICH I， DRESSLER F. On the lifetime of wireless sensor networks [J]. ACM transactions on sensor networks， 2013， 5（1）： 34?41.

[4] GUO W， ZHANG W. A survey on intelligent routing protocols in wireless sensor networks [J]. Journal of network & computer applications， 2014， 38（1）： 185?201.

[5] CADGER F， CURRAN K， SANTOS J， et al. A survey of geographical routing in wireless Ad?Hoc networks [J]. IEEE communications surveys & tutorials， 2013， 15（2）： 621?653.

[6] ABD M A， SINGH B K， RUBEAAI S F A， et al. Game theoretic energy balanced （GTEB） routing protocol for wireless sensor networks [C]// Proceedings of 2014 IEEE Wireless Communications and Networking Conference. Istanbul： IEEE， 2014： 2564?2569.

[7] CHEN Y S， LIN Y W. Mobicast routing protocol for underwater sensor networks [J]. IEEE sensors journal， 2013， 13（2）： 737?749.

[8] AYAZ M， BAIG I， ABDULLAH A， et al. A survey on routing techniques in underwater wireless sensor networks [J]. Journal of network & computer applications， 2011， 34（6）： 1908?1927.

[9] BOUABDELLAH K， NOUREDDINE H， LARBI S. Using wireless sensor networks for reliable forest fires detection [J]. Procedia computer science， 2013， 19（2）： 794?801.

[10] KADI M， ALKHAYAT I. The effect of location errors on location based routing protocols in wireless sensor networks [J]. Egyptian informatics journal， 2015， 16（1）： 113?119.

[11] ARSLAN M G， ONEL T， ERSOY C. Effect of 3D topographical surfaces for the performance evaluation of wireless sensor networks [C]// Proceedings of IEEE the 19th International Symposium on Personal， Indoor Mobile Radio Communications. Cannes： IEEE， 2008： 1?6.

[12] POMPILI D， MELODIA T， AKYILDIZ I F. Three?dimensional and two?dimensional deployment analysis for underwater acoustic sensor networks [J]. Ad Hoc networking， 2013， 7（4）： 778?790.

[13] AMUNDSON I， KOUTSOUKOS X D. A survey on localization for mobile wireless sensor networks [C]// Proceedings of 2011 International Conference on Mobile Entity Localization and Tracking in GPS?Less Environments. Berlin， Germany： Springer?Verlag， 2011： 235?254.

[14] Information Sciences Institute. Transmission control protocol， RFC 793 [EB/OL]. [2015?10?21]. https：//tools.ietf.org/html/rfc793.

[15] OpenSim Ltd. OMNeT++ discrete event simulator [EB/OL]. [2015?10?21]. https：//omnetpp.org/.