基于PLC的地下綜合管廊數(shù)據(jù)傳輸算法及仿真

劉 航，邊 帥，王 惠，王 穎

(1. 重慶梅安森科技股份有限公司，重慶 400039；2. 重慶郵電大學計算機科學與技術學院，重慶 400065)

1 引言

地下綜合管廊是由隧道中的電力、通訊、燃氣、給排水等各種管道構(gòu)成的地下管網(wǎng)系統(tǒng)[1，2]，是一種集約化、現(xiàn)代化的城市公用基礎設施。目前，隨著建設智慧城市的發(fā)展，越來越多的新一代信息技術被運用到城市綜合管廊的管理和監(jiān)控中。如利用無線傳感器網(wǎng)絡(Wireless Sensor Network，WSN)對市政管道破損以及運行狀態(tài)進行實時監(jiān)測等[3]。但WSN在地下傳輸具有通信距離短、傳輸不可靠、部署困難等缺點。電力線載波通信(Power Line Communication，PLC)網(wǎng)絡是一種將現(xiàn)有的電力線路作為傳輸媒介，在傳輸電能的同時傳輸數(shù)據(jù)的網(wǎng)絡。近年來廣泛應用于工業(yè)現(xiàn)場設備監(jiān)控[4]、水電氣遠程抄表[5]和油水監(jiān)測[6]等領域。基于PLC技術的地下管廊數(shù)據(jù)傳輸系統(tǒng)具有可靠性高、易部署、成本低等優(yōu)勢。地下管廊中部署的PLC節(jié)點能感知、采集和處理網(wǎng)絡覆蓋區(qū)域內(nèi)的監(jiān)測信息，并發(fā)送給中央?yún)f(xié)調(diào)控制器(Central Coordinator，CCO)。CCO通常位于管廊的出口處，部分節(jié)點部署距離較遠，需要采用多跳單播路由的方式與CCO進行通信。因此，如何通過PLC多跳路由自組網(wǎng)方式，實現(xiàn)監(jiān)測數(shù)據(jù)的遠距離、高可靠傳輸，成為目前的研究熱點之一。

文獻[7]提出了一種基于PLC的路由樹形拓撲快速形成算法。文獻[8]針對PLC網(wǎng)絡提出了一種分層路由管理機制，該路由機制能有效提高通信成功率和實時性。文獻[9]提出一種基于節(jié)點可靠性計算的多路徑路由算法。文獻[10]提出一種利用節(jié)點的地理位置信息形成單播路由，能有效的減少節(jié)點能量消耗和傳輸時延，但并未考慮網(wǎng)絡的可靠性。文獻[11]研究了一種利用網(wǎng)絡拓撲的靜態(tài)信息和網(wǎng)絡性能參數(shù)，以此確定路徑的路由算法，算法能有效的適應動態(tài)PLC網(wǎng)絡，避免了通信中不必要的能量消耗，但可靠性不高。文獻[12]提出分布式機會路由算法，該算法以時延為約束確定轉(zhuǎn)發(fā)列表優(yōu)先級，最終形成最優(yōu)路由，但對節(jié)點性能要求較高。文獻[13]以時延、可靠性和發(fā)射功率為約束，提出一種改進的遺傳算法來選擇中繼節(jié)點的路由算法。

基于以上研究成果，本文提出一種結(jié)合管廊節(jié)點位置和節(jié)點鏈路狀態(tài)信息對中繼節(jié)點進行選擇的路由算法(Geographic Location and Link State，GLS)。該算法根據(jù)節(jié)點間的鏈路狀態(tài)信息及載波節(jié)點地理位置，力求構(gòu)建出更加符合地下綜合管廊的樹狀路由拓撲網(wǎng)絡。算法同時考慮到地下節(jié)點分布不均勻以及業(yè)務數(shù)據(jù)突發(fā)性等因素，對路由樹進行調(diào)整，來解決各種動態(tài)場景下負載不均衡，導致丟包較多的問題。該算法能減少傳輸時延及丟包率，且具有較好的適應性和擴展性。

2 系統(tǒng)模型和網(wǎng)絡結(jié)構(gòu)

地下管廊是一種半封閉的空間，假設網(wǎng)絡由若干個節(jié)點組成，分布在一個矩形區(qū)域內(nèi)，節(jié)點需要周期性向上傳輸數(shù)據(jù)，考慮PLC線路節(jié)點有效傳輸距離不穩(wěn)定的特性以及樹型結(jié)構(gòu)構(gòu)造簡單、易于擴展、便于延伸分支和新節(jié)點加入，大部分PLC路由協(xié)議均采用樹型結(jié)構(gòu)。圖1為單向電力線載波接入網(wǎng)絡邏輯拓撲結(jié)構(gòu)圖。

圖1 管廊網(wǎng)絡通信模式示意圖

網(wǎng)絡中包括三種節(jié)點：集中控制協(xié)調(diào)器(CCO)、普通節(jié)點和中繼節(jié)點。集中控制協(xié)調(diào)器具有較強的計算和存儲能力，運行路由協(xié)議，負責網(wǎng)絡的路由維護和操作指令的下發(fā)。所有節(jié)點之間傳輸數(shù)據(jù)以及訪問外部網(wǎng)絡都要通過集中控制器。控制器到網(wǎng)絡中的任何普通節(jié)點至少有一條路徑可供選擇。除了集中控制器以外的所有節(jié)點都為普通節(jié)點，它負責本地數(shù)據(jù)采集與發(fā)送。同時，任何普通節(jié)點均可以被選擇作為中繼節(jié)點，承擔著初始化節(jié)點路由表、解析數(shù)據(jù)包和數(shù)據(jù)存儲轉(zhuǎn)發(fā)等任務。

根據(jù)管廊環(huán)境特征，網(wǎng)絡模型假設節(jié)點具有以下特性：

1) 控制器位于網(wǎng)絡外側(cè)，其計算能力和存儲能力不受限制，部署到網(wǎng)絡后位置固定不變。

2) 集節(jié)點同構(gòu)并具有相同的發(fā)射功率，每個節(jié)點具有全網(wǎng)唯一的標識號。

3 地理位置與鏈路狀態(tài)結(jié)合的PLC路由算法

3.1 算法概述

許多基于PLC網(wǎng)絡的路由協(xié)議并沒有直接考慮網(wǎng)絡節(jié)點的實際地理位置，僅是根據(jù)節(jié)點間鏈路的邏輯連接情況進行路由的設計。在地下管廊中使用基于鏈路狀態(tài)形成的最短路徑不一定為最優(yōu)路徑，有可能在該路徑上節(jié)點稀疏，連接性不好，導致路由時延和丟包率較大；還有可能獲得一條存在較多冗余中繼節(jié)點的路徑。因為在實際的PLC網(wǎng)絡中，邏輯距離與實際的物理距離并沒有明顯的定量關系。雖然載波接收信號強度能反應各個采集節(jié)點之間的信道載波傳輸鏈路狀態(tài)，但僅根據(jù)鏈路狀態(tài)確定中繼節(jié)點存在明顯不合理性，可能增加整個路由的轉(zhuǎn)發(fā)跳數(shù)，導致網(wǎng)絡性能下降。為了提升網(wǎng)絡效率，形成一棵更高效的路由樹，本文提出一種結(jié)合地理位置與鏈路狀態(tài)的路由選擇算法(GLS)，算法以最小信號強度衰減和最佳地理位置為目標，建立節(jié)點與控制器的最佳傳輸路徑。

3.2 中繼節(jié)點選擇策略

節(jié)點間的信號質(zhì)量是評估節(jié)點間通信可靠性的一項重要指標，因而節(jié)點能作為中繼節(jié)點的條件之一是接收信號強度需達到一個最低的限度。然而，接收信號太強，可能意味著具有較小的物理距離，導致形成的路由具有較多的轉(zhuǎn)發(fā)跳數(shù)；而接收信號太弱會導致數(shù)據(jù)傳輸不可靠。因此，如果存在可供選擇的多個中繼節(jié)點，需根據(jù)信號強度確定一個上下閾值Tl和Tu。因此信號強度應該滿足以下條件

Tl≤SBij≤Tu

(1)

Tl≤SBji≤Tu

(2)

i∈SubNode，j∈hopNode

(3)

其中，其中j為各跳中繼節(jié)點hopNode，i為中繼節(jié)點的子節(jié)點SubNode，SB為信號強度。式(1)表示子節(jié)點到中繼節(jié)點的通信要滿足信號強度的要求；式(2)表示中繼節(jié)點到其子節(jié)點的通信也要滿足信號強度的要求。

另外，還要考慮節(jié)點的地理位置，即節(jié)點與鄰居間的物理距離以及節(jié)點與集中控制器間的距離。接收信號強度強且物理距離較遠的節(jié)點具有較高的轉(zhuǎn)發(fā)優(yōu)先級，該策略可以讓數(shù)據(jù)到達目的節(jié)點前經(jīng)歷較少的轉(zhuǎn)發(fā)次數(shù)，從而保證每次中繼的“距離跨度”。在如圖2所示的網(wǎng)絡中，假設節(jié)點C與節(jié)點D距離S的物理距離相同，并且它們接收到S的信號強度相同。選擇節(jié)點C為中繼節(jié)點，只需一跳既可到達目標節(jié)點T。而選擇節(jié)點D為中繼節(jié)點，則數(shù)據(jù)需要借助E轉(zhuǎn)發(fā)才可以到達目標節(jié)點T。這種基于地理位置的最大“距離跨度”中繼節(jié)點選擇策略，可以使數(shù)據(jù)以最少跳數(shù)到達目的節(jié)點，從而提高系統(tǒng)效率，減少轉(zhuǎn)發(fā)時延。

圖2 結(jié)合地理位置的中繼節(jié)點選擇策略示意圖

3.3 路由算法流程及步驟

本文提出的路由算法將形成一個樹形結(jié)構(gòu)網(wǎng)絡拓撲圖。樹的根節(jié)點為CCO，對整個網(wǎng)絡的路由和連接進行管理。網(wǎng)絡中所有的一跳節(jié)點可以直接與CCO進行通信，其它節(jié)點可通過一個或多個中繼節(jié)點與CCO進行通信。

路由樹形成過程算法1所示。其核心思想為：CCO依次輪詢各個節(jié)點，根據(jù)信號強度選擇出一跳節(jié)點；根據(jù)地理位置從一跳節(jié)點中選擇出一跳中繼節(jié)點；依次選擇出后續(xù)各跳節(jié)點及中繼節(jié)點。其中hopNodek為各跳中繼節(jié)點集合，hopListk為各跳節(jié)點集合，其中k為跳數(shù)。當k=0時，hopNode0中只有CCO一個節(jié)點，表示一跳節(jié)點的中繼節(jié)點為CCO。第32行中，從k跳節(jié)點中選擇k跳中繼節(jié)點的方法采用3.2節(jié)中的中繼節(jié)點選擇策略進行選擇，盡可能選擇地理位置較遠的節(jié)點為中繼節(jié)點，減少中繼節(jié)點跳數(shù)。

算法1在形成路由樹的過程中，節(jié)點與其鄰居節(jié)點發(fā)生入網(wǎng)請求的總次數(shù)N可描述為

(4)

(5)

其中，n表示所有節(jié)點數(shù)量(不包括CCO)nk表示k跳中繼節(jié)點的數(shù)量，rk表示k-1跳節(jié)點組網(wǎng)后剩余節(jié)點數(shù)量。式(4)中的每一項表示k跳中繼節(jié)點從剩余節(jié)點中選取下一跳節(jié)點的入網(wǎng)請求次數(shù)。假設每一個節(jié)點至少能與其中一個節(jié)點通信，那么算法的最壞情況是每一跳只有一個節(jié)點，整棵路由樹共有n跳。此時，算法獲得此路由樹，需要的入網(wǎng)請求次數(shù)Nmax可以表述如下

(6)

綜上所述，算法最壞情況下的組網(wǎng)復雜度為O(n2)。因此，算法的平均復雜度不超過O(n2)。在經(jīng)典的路由算法OSPF中，采用最短路徑優(yōu)先的原則生成路由樹，其算法的復雜度也為O(n2)。所以，本文提出的算法與OSPF算法復雜度相同。

3.4 新節(jié)點入網(wǎng)

考慮管道部署環(huán)境的特殊性以及對網(wǎng)絡拓撲結(jié)構(gòu)變化具有較好的適應性和擴展性，本算法也提出新節(jié)點入網(wǎng)算法。在若干數(shù)據(jù)傳輸周期結(jié)束后會留出一個新節(jié)點競爭入網(wǎng)時隙。未入網(wǎng)節(jié)點偵聽到附近節(jié)點的數(shù)據(jù)幀并從payload部分中解析出競爭開始的時間值。當競爭時間到來時，未入網(wǎng)節(jié)點根據(jù)接收信號強度選擇一個最優(yōu)的節(jié)點單播發(fā)送入網(wǎng)請求幀。接收到新節(jié)點入網(wǎng)請求信息的節(jié)點將該信息保存下來，當CCO輪詢時，節(jié)點將該信息封裝在payload中發(fā)送給CCO。如果CCO允許該節(jié)點入網(wǎng)，CCO向其回應一個確認幀并將該節(jié)點加入路由樹和HopList中，完成新節(jié)點入網(wǎng)。

3.5 路由優(yōu)化和負載均衡

在該多跳路由樹中，如果某個中繼節(jié)點比同跳數(shù)的其它中繼節(jié)點擁有更多的子節(jié)點，會造成數(shù)據(jù)流量在不同路徑上分布不均勻，導致部分路徑負載過重，從而引起丟包甚至網(wǎng)絡崩潰。因此，某負載較重中繼節(jié)點可能成為網(wǎng)絡瓶頸，給管廊數(shù)據(jù)傳輸帶來嚴重后果[10]。為了形成合理的網(wǎng)絡拓撲結(jié)構(gòu)，達到數(shù)據(jù)流量均衡分布的目的，需要對GLS路由樹進行優(yōu)化，形成更為優(yōu)化的負載均衡路由樹。本節(jié)提出一種負載均衡算法，對GLS形成的網(wǎng)絡路由樹進行調(diào)整，稱之為Improve-GLS算法。該算法可以讓CCO改變某些葉子節(jié)點的中繼節(jié)點，從而實現(xiàn)負載均衡的目的。

定義子樹負載均衡指數(shù)為SBIj(Sub-tree Balance Index)，其為中繼節(jié)點j的所有子節(jié)點的子樹上最多的節(jié)點數(shù)量與最少的節(jié)點數(shù)量之差。SBIj越接近于0，說明子樹均衡程度越好。

SBIj=Num(imax)-Num(imin)

(7)

SubNode(j)表示節(jié)點j的所有子節(jié)點集。Num(i)表示以中繼節(jié)點j的各子節(jié)點為根節(jié)點的子樹的節(jié)點數(shù)量。Num值越大，表示中繼節(jié)點j的子節(jié)點負載越大。其中，中繼節(jié)點j負載最大的一個子節(jié)點可以用如下方式表示：

imax=arg maxiNum

(8)

找到中繼節(jié)點j負載最大的一個子樹后通過對子節(jié)點進行調(diào)整，從而實現(xiàn)負載均衡。在優(yōu)化過程中，CCO按照與其邏輯距離的從遠到近進行遍歷，要求每個中繼節(jié)點對SBIi進行檢測和調(diào)整，具體步驟如算法2所示。

3.6 路由算法流程及步驟

CCO承擔了全部的路由決策任務，存有到達所有目標節(jié)點的路徑信息，它將該路徑上每一跳所要經(jīng)過的中間節(jié)點地址都填到數(shù)據(jù)包頭部，然后“下行”轉(zhuǎn)發(fā)給目標節(jié)點。下行路徑所經(jīng)過的每一跳中間節(jié)點，都按照數(shù)據(jù)包頭部路徑信息的指示，向下一跳轉(zhuǎn)發(fā)，最終到達目標節(jié)點。任何節(jié)點需要給CCO發(fā)送信息，只需要將信息發(fā)送給該節(jié)點的父節(jié)點，經(jīng)過多次轉(zhuǎn)發(fā)后，最終將數(shù)據(jù)包發(fā)送給CCO。

算法采用“下行源路由+上行普通路由”機制，可避免節(jié)點維護大量路由信息，減少節(jié)點存儲空間需求。但該算法增加了每個數(shù)據(jù)包的長度開銷?？紤]到管廊中幾乎所有節(jié)點均為電源供電，對能耗并不敏感，采用該方式較合理。

4 仿真及分析

4.1 實驗設置

為了驗證GLS和Improve-GLS算法的性能，本文使用Matlab作為仿真工具，對網(wǎng)絡中的時延、吞吐量和丟包率性能進行仿真分析。在300m×350m的區(qū)域散布42個節(jié)點，CCO位于(200，0)，邏輯ID為1，其余節(jié)點編號依次為2到43，假設網(wǎng)絡中不存在孤立節(jié)點，節(jié)點距CCO最多為四跳，所有的節(jié)點共享同一信道，網(wǎng)絡拓撲如圖3所示。每個節(jié)點以固定速率發(fā)送數(shù)據(jù)包，每個數(shù)據(jù)包大小為1000位，仿真時間為1800秒。與文獻[11]提出的基于鄰居節(jié)點信息的路由算法NKR(Neighborhood Knowledge based Routing)和經(jīng)典的OSPF (Open Shortest Path First)算法進行比較。

圖3 網(wǎng)絡拓撲結(jié)構(gòu)圖

4.2 實驗結(jié)果及分析

圖4描述了各節(jié)點發(fā)送數(shù)據(jù)的端到端的平均時延?？煽闯霰疚奶岢龅腉LS算法在時延方面優(yōu)于NKR。主要原因為NKR需要不斷收集鄰居節(jié)點信息，每次轉(zhuǎn)發(fā)都需要重新計算路由。而GLS在路由計算階段已獲得數(shù)據(jù)轉(zhuǎn)發(fā)路徑，因此幾乎所有節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)時延性能均表現(xiàn)良好(僅節(jié)點12、15、27、30時延比NKR算法略差)。

圖4 所有節(jié)點端到端平均時延

圖5和圖6描述了GLS、Improve-GLS和OSPF算法在不同數(shù)據(jù)包發(fā)送速率下的丟包率和時延。由圖5所知，隨著發(fā)送速率的增大，各個算法的丟包率有所增加，但是GLS和Improve-GLS的丟包率增幅明顯低于OSPF算法。在仿真的過程中，選取5個距離集中控制器最遠的節(jié)點作為測試節(jié)點，統(tǒng)計這5個節(jié)點產(chǎn)生的數(shù)據(jù)包傳輸?shù)紺CO的時間作為端到端的傳輸時延。由于數(shù)據(jù)流量較大時，數(shù)據(jù)傳輸沖突加劇，導致發(fā)送緩存隊列增長，從而增加了端到端的數(shù)據(jù)傳輸時延，但GLS和Improve-GLS遠遠好于OSPF。

圖5 不同數(shù)據(jù)包發(fā)送速率對丟包的影響

圖6 不同數(shù)據(jù)包發(fā)送速率對時延的影響

5 結(jié)論

由于地下管廊通信環(huán)境復雜，無線傳輸在此環(huán)境中存在丟包率高和時延大等問題，本文提出一種基于PLC的多跳路由算法實現(xiàn)地下管廊系統(tǒng)的數(shù)據(jù)傳輸。算法結(jié)合節(jié)點的鏈路狀態(tài)和地理位置信息構(gòu)建拓撲路由樹，實現(xiàn)數(shù)據(jù)多跳傳輸。另外，算法考慮到地下節(jié)點分布不均勻等因素，根據(jù)子樹的負載均衡指數(shù)對不均衡路由子樹進行優(yōu)化和調(diào)整，實現(xiàn)路由樹負載均衡。通過仿真驗證，提出的算法在時延和丟包率等方面均有較好的性能表現(xiàn)。