認知社會物聯網中能量感知的編碼機會路由協議

鐘曉雄 陸 瑛 農英雄 陳智斌 孫 忱 盧仁浩

1(桂林電子科技大學廣西可信軟件重點實驗室 廣西 桂林 541004)2(廣西中煙工業有限責任公司信息中心 廣西 南寧 530001)

0 引 言

隨著計算機網絡與通信技術的高速發展，物聯網[1]吸引了許多學術界、產業界學者的重點關注。物聯網中海量的異構設備互聯可以應用不同的場景，比如智慧家庭、智慧城市、智慧醫療等。其中社會物聯網[2](Social Internet of Things，SIoT)是物聯網的一個分支，它是在物與人之間構建社會圖，并以此模式進行數據傳輸。目前在物聯網路由研究領域的相關工作比較少。針對物聯網的應急響應問題，Qiu等[3]提出了一種利用全局信息決策的保障物聯網可靠傳輸的路由協議。Marco等[4]提出一種MAC感知的跨層優化的路由協議，它兼顧了傳輸可靠性和網絡生存時間。但上述兩種路由協議均未考慮到頻譜資源對路由設計的影響。認知無線電技術(cognitive radio,CR)[5]可以提高頻譜資源的使用率。面對海量設備的接入，如何利用CR技術提高頻譜資源及數據傳輸可靠性顯得尤為重要。機會路由(opportunistic routing,OR)[6]充分利用無線信道的廣播特性，機會地傳輸數據，進而可以提供網絡傳輸性能，如提供傳輸可靠性、減少傳輸次數等。在機會路由中，節點廣播信息至其候選集節點，然后其候選集節點都有機會被選中用以傳輸數據，它們是合作地傳輸數據。由于認知社會物聯網特性，機會路由這種不需要提前決定好端到端路徑的路由機制非常適合。

針對認知無線網絡機會路由中，研究者已經提出了一些方案。Pan等[7]給出了一種基于包傳輸率的優先級確定規則及最優候選集選擇算法。文獻[8-9]主要利用頻譜資源的可用時間優化路由設計問題。Lin等[10]為了保障單信道認知物聯網中的吞吐量，提出了一種頻譜感知的機會路由協議。同時，針對多信道環境問題，文獻[11]進一步完善了頻譜感知的機會路由機制問題。通過利用基于局部信息構建的頻譜信息圖來設計機會路由。同時考慮鏈路質量及隨機幾何以設計地理位置機會路由。Liu等[12-13]基于異質信道占用模型，利用統計信道使用率及無線信道的物理容量作為路由決策標準，同時給出了最優候選集選擇算法。文獻[14]提出了一種聯合信道分配與編碼機會路由優化模型及一種啟發式候選集及信道分配算法。同樣地，Zheng等[15]提出了一種編碼與頻譜感知的機會路由協議。Cui等[16]基于接入機會和傳輸時延設計新的機會路由協議，同時為了改善頻譜可利用性，還提出了一種雙階段合作頻譜感知策略。Tang等[17]提出了一種基于網絡編碼和地理位置的機會路由協議，其主要目的是最小化平均傳輸次數。Barve等[18]提出一種聯合考慮信道分配與增強學習的機會路由協議。在所提協議中，采用了一種在線更新路由信息的方法以更加準確地發現傳輸機會。Cai等[19]基于信道感知，候選集選擇及包分發等目標，提出了一種跨層的最小化時延優化機會路由協議。Dai等[20]提出了一種雙層的候選集選擇算法，用以更加可靠地傳輸數據，它可以在一定程度上解決通信信道上由于PU突然到來引起的中斷問題。Lin等從機會路由的角度提出了一種保障QoS的控制機制，實現了虛擬會話級別的MIMO通信。同時，為了解決衰減干擾和候選集選擇問題，Lin等[22]進一步研究了機會路由協議并提出了一種認知與機會式的候選集選擇算法。然而，上述所有的研究工作都沒有考慮區分服務問題，針對此問題，How等[23]提出了一種面向區分服務的機會路由協議，聯合考慮信道的可用性和時延特性以優化數據機會傳輸及功率控制。但文中并沒有考慮到社會屬性對機會傳輸的影響以及重傳次數問題。受此問題啟發，本文提出了一種面向多業務流的社會感知的編碼機會路由ECOR(energyaware coded opportunistic routing)，同時考慮了信道分配問題。表1給出了不同機會路由的特性。

表1 認知無線網絡中機會路由協議對比

續表1

本文的創新點可以歸納為：

1) 綜述了近年來認知物聯網中關于機會路由研究現狀并給出了本文研究的動機，提出了一種面向多業務流的聯合社會感知的編碼機會路由和基于博弈論的信道分配策略。

2) 本文證明機會路由中候選集的選擇是一個NP-hard問題。因而，我們采用了一直近似算法來解決此問題。提出了聯合考慮社會屬性與能耗問題的路由度量標準，進而提出一種新的基于拍賣模型的候選集選擇算法，并求出其最優解。

3) 為了提高數據傳輸高效可靠性，在數據傳輸過程中，我們采用網絡編碼技術進行傳輸數據，加快數據高效可靠傳輸進程。同時給出了一種基于流優先級確定算法和基于干擾圖的博弈信道分配算法。

4) 通過實驗仿真驗證了所提策略的有效性，主要從包投遞率、平均時延和跳數三方面與現有工作進行對比。

1 能量感知的編碼機會路由協議

在本節中，我們對所提機會路由協議進行詳細的描述。我們給出了網絡模型及路由度量標準的構建，基于此，提出了基于拍賣模型的候選集選擇算法，同時給出了一種基于博弈論的信道分配算法。為了加快數據可靠快速傳輸，在數據傳輸過程中，采用了網絡編碼技術。

1.1 網絡模型

本文的網絡拓撲結構如圖1所示，它由主用戶系統(Primary System)和次用戶系統組成。其中，在次用戶系統中，次用戶之間的通信受它們之間的社會關系和主用(primary users,PUs)的影響。SU機會式使用當前PU未使用的信道。如在數據傳輸(SU2->SU8)中，因為社會屬性，在同等條件下它會選擇SU7為中繼節點進行數據傳輸，而不考慮SU6。

圖1 認知社會物聯網

在ECOR中，我們采用interweave模型[14]，在此模型中，信道采用的是時分復用技術，固定的時隙長為T，包括數據傳輸時長Tt和感知時長Ts，并且有(Tt=T-Ts)。此模型中有C個信道，nums個SUs和nump個PUs。每個節點都配置相同的射頻數R，并工作于半雙工模式。信道的使用模型為獨立ON/OFF模型，并滿足指數分布，速率參數分別為λbusy和λidle。

1.2 基于拍賣模型的候選集選擇算法

在本小節中，我們將介紹所提機會路由協議中的候選集選擇算法，主要包括基于社會屬性，能量與期望傳輸次數的路由度量標準，拍賣模型構建。

1.2.1社會關系刻畫

在現實生活中，攜帶智能設備(即本文中的SU)通常擁有一定的社會關系，如擁有相同的興趣，家庭關系等。我們通過歷史信息來刻畫節點間的社會關系，比如相遇頻繁率、社會相似度等。本文采用以下社會關系(social ties，ST)來描述節點間的社會屬性，進而用以加快數據傳輸進程。

STi,j(T)=χSPMi,j(T)+(1-χ)socsimi,j(T)

(1)

式中：SPMi,j(T)為節點i和j之間在時間段T內的社會關系度量標準[24]χ(∈[0,1])為權重因子，在仿真實驗中設置為0.5。socsimi,j(T)為節點i和j之間在時間段T內社會相似度，它可以通過以下公式計算：

socsimi,j(T)=comi,j(T)/(ni(T)+nj(T))

(2)

式中：comi,j(T)為節點i和j之間在時間段T內相同的鄰居節點數目,ni(T)和nj(T)分別為節點i和j在時間段T內的一跳鄰居節點數目。

1.2.2能 耗

假設EiC(T)為節點i在時間段T內成功傳輸一個數據包至其下游節點消耗的能量，主要包括三部分：轉發數據包能耗EiF(T),收到/監聽一個數據包的能耗EiR(T)，發送一個ACK包的能耗EiACK(T)，則有：

EiC(T)=EiF(T)+Nc×EiR(T)+EiACK(T)

(3)

式中：Nc節點i在時間段T內的一跳鄰居節點數目。同時，假設能量消耗滿足(0,1)均勻分布。

1.2.3拍賣模型

(4)

在候選集中CFS選擇一組節點CFS′使得u0(CFS′)為所有節點子集中最大化，我們稱之為候選集選擇問題，其是一個NP-hard問題，接下來我們給出了證明過程。

定理1在ECOR中，候選集選擇問題是一個NP-hard問題。

證明：如我們所知集合覆蓋問題是NP-hard問題。因而只要證明候選集選擇問題為集合覆蓋問題即可證明定理1。假設在集合覆蓋問題的一個實例中：集合U={u1,u2,…,um}，CFS={CFS1,CFS2,…,CFSn}為U的子集和一個正整數d。那么是否存在元素為d的任何子集CFS′?CFS使得任何U的一個元素至少屬于CFS′？接下來我們證明其充要條件。

充分條件：假設CFS′為集合覆蓋問題的一個實例，那么我們可以選擇對應候選集CFS′為集合覆蓋問題的實例，且易得到u0(CFS′)=mn-|CFS′|≥nm-d。

必要條件：假設CFS′為候選集選擇問題的一個實例，則有u0(CFS′)=mn-|CFS′|≥nm-d。要得到這個值，只有一種可能性：所選的候選集覆蓋在d≤m條件下的所有候選集。因此，可以看出CFS′是一個集合覆蓋問題的實例。

綜述所述，定理1證明完畢。

由定理1可知，在所提機會路由中，選擇最優候選集問題是一個NP-hard,因此，我們必須采用近似或者啟發式的算法求解。接下來，我們提出一種啟發式的候選集算法，包括路由度量標準及候選集選擇算法。

在所提機會路由中，路由度量標準主要考慮社會屬性，能耗及期望傳輸次數，我們通過以下公式計算其值。

ECORi,j(T)=φ1ETXi,j(T)+φ2EiC(T)+φ3/STi,j(T)

(5)

式中：ETXi,j(T)為節點i和j之間在時間段T內的期望傳輸次數ETX(Expected Transmission Count)，φ1、φ2、φ3為權重參數，并且有φ1+φ2+φ3=1。

算法1候選集選擇算法

1:CFSv,1←?,CFSv,2←?,CFSv←?

2:for所有節點j∈N(v)do

3: 根據式(5)-式(6)計算路由度量值和閾值

4:if(ETORi(T)≤ETORthreshold(T))&&

(Ch(v)∩Ch(j)≠?)

&&(Ch(j)∩Ch(N(j))≠?)then

5:CFSv←CFSv∪j

6:endif

7:endfor

8: 對CFSv進行劃分，其中一半候選節點存于CFSv,1,另一半存于CFSv,2

9:returnCFSv,1,CFSv,2

在選擇候選集時，我們根據以下路由度量標準閾值來保證所選的候選集為可靠通信節點，即ECORi(T)≤ECORthreshold(T)。在實際中，ECORthreshold(T)可表示為：

(6)

式中：N(i)為節點i一跳候選集。

為了傳輸可靠性及網絡負載均衡，在所選的候選集中，我們對其進行一分為二，其中前半部分為CFSi,1，另外一半為CFSi,2。

在候選集選擇算法中，s為任何一個節點(除源節點和目的節點)，N(v)節點v的一跳節點集，Ch(v)為v的可用信道，CFSv為v候選集。

因此，根據上述建立的博弈模型，節點i的平均轉發代價可表示為:

(7)

式中：ETXi為節點i至目的節點D的ETX。

根據上述假設EiC為(0,1)均勻分布，可得：

(8)

式中：ETXs為源節點s至目的節點D的ETX，Einitial為初始能量。同時易知vi為(0,1)均勻分布。

根據貝葉斯納什均衡可得節點i的期望利潤：

(9)

式中：P(bi<(b(vj))節點i出最低價格的概率，b(v)為策略函數，且為關于v的嚴格單調遞增函數。

根據vi的特性，可得：

P(bi<(b(vj))=P(Φ(bi)

(10)

和

(11)

式中：Φ(b)為b(v)的反函數。

因此，我們有：

maxui=maxbi((bi-vi)[1-Φ(bi)]|CFSi|-1)

(12)

故可以求得最優出價：

(13)

同時，可以依據這個價格來確定轉發優先級。擁有低價格的節點具有較高轉發優先級。

1.3 基于博弈的信道分配

在機會路由中，候選集選擇必須考慮信道分配以提高數據傳輸效率及信道使用率。因此，在本文中我們提出了一種基于博弈的信道分配算法：某段時間T內最小化信道干擾。假設信道ci和cj的干擾函數為ISci,Scj(T)。參與人集P={P1,P2，…,Pn}和參與人所選策略Sci。

(14)

因此，效用函數可表示為：

(15)

式中：Nij為ci與cj間的射頻對。

根據納什均衡[25]可得：

(16)

定理2在所提博弈模型中，至少存在一個納什均衡解。

綜上所述，定理2證明完畢。

接下來，我們給出了基于博弈論的信道分配算法，如算法2所示。在算法2中，假設信道一旦被分配則立即傳輸數據，當PU出現在所分配的信道上，則更新節點擁有的信道信息。

算法2基于博弈論的信道分配算法

i為網絡中運行算法2的節點，Ch(i)為節點i的可用信道集合，C(R)為分配給射頻R的信道集合。

1:Input:i,Ch(i)

2:whileCh(i)≠?do

3: 根據式(15)計算效率值并且存入A中

4:endwhile

5: 根據A中元素值按遞增次序對其元素進行排序

6: 根據進行U(·)分配信道

7: 把分配完的信道存入C(R)中

8:OutputC(R)

1.4 基于網絡編碼的數據傳輸

在ECOR中,在所選節點之間我們采用網絡編碼[26]技術用以加快數據傳輸進程。源節點把需要傳輸數據分成小塊，每塊含有k個數據包形如：PKT1,PKT2,…,PKTk，我們稱之為原始包。然后源節點對k個數據包進行線性組合并進行發送。中間節點收到后進行判斷，如果線性無關則編碼后進行傳輸，目的節點收到足夠多(大于等于k)時，進行解碼操作，恢復出k個原始數據包。在ECOR，k的值設置為10。與文獻[27]相似，我們采用信用計數器作為是否編碼和轉發的條件。每個信道對應一個信用計數器。因而，一個節點有|C|個信用計數器。信用計數的值可通過下式來計算：

(17)

式中：u(c)為信道可用概率，ρji(c)為節點j和i在信道c上的丟包率，zi(c)為期望傳輸次數。如果crediti(c)為正數，則節點產生一個編碼包，并在信道c廣播，然后計數器減1。否則不執行編碼及轉發操作。

在認知社會物聯網中，存在多種類型業務流，因此，在所提機會路由中，我們在基于網絡編碼技術的數據傳輸中考慮了業務多樣化特性。假設在中繼節點中，存在多種業務流，那么轉發的規則如下：

1) 對于不同的業務流，轉發優先級按照事先約定好的進行轉發。

2) 對相同的業務流，根據ζfi值大小進行轉發，值越大轉發優先級越高。

ζfi=δ1nfi(pkt)+δ2nfi(times)

(18)

式中：δ1和δ2為權重因子，并且有δ1,δ2∈[0,1]，在仿真實驗中兩者都設置為0.5，nfi(pkt)為當前節點i中流fi所有包數，nfi(times)為流fi經過當前節點i的次數。

2 性能評估

在本節中，我們對所提的機會路由ECOR進行性能評估，主要仿真環境為NS2[28]，CRCN模塊[29]和MIT真實數據集[30]。仿真參數設置如下：

SUs的移動模型為random waypoint模型，其所在一個節點密度為400 nodes/km2的區域，SUs的傳輸范圍為120 m，PUs為固定位置，且傳輸范圍為300 m，PU數目為10。信道數目為10，且工作于IEEE 802.11b傳播模型為Two-Ray Ground。CBR包大小為1 000字節。SU產生業務流即刻隨機選擇一個目的節點。射頻數目為2。帶寬為5.4 MB/s。仿真時間為1 000 s。業務流產生的時間間隔為[60 s,1 000 s]，路由度量標準的參數分別設置為0.4，0.3和0.3。對仿真實驗我們執行100次并對下面考核性能指標求平均值：包投遞率、跳數和平均端到端時延。能量模型中的參數設置EiF(T)、EiR(T)、EiACK(T)分別為3.6e-3 eu、1.8e-3 eu、0.16e-3 eu。節點的初始能量為300 eu。假設網絡中存有三種類型的業務流，每種業務流數目為5，它們的優先級如表2所示。仿真實驗參數設置如表3所示。在仿真實驗結果中，我們對比了以下四種路由協議：MOR[20](基于雙層候選集選擇的機會路由協議)、OSDRP[23](面向不同業務流的機會路由協議)、CAODV[31](面向認知無線網絡的AODV協議)和SoRoute[32](認知無線網絡中基于社會屬性的路由協議)。

表2 三種業務流的MAC參數設置

表3 仿真參數設置

1) 信道數目對性能的影響。在本組實驗中，我們評估了信道數目對平均時延，跳數及包投遞率等性能的影響。PUs、SUs數目分別設為10和50，PU的活動參數設為200 s。

從圖2，圖3可以看出，隨著信道數目的增加，平均時延和跳數先從開始增加，然后趨于平穩。這是因為如果信道更多的話，那么數據得以傳輸的機會就越多。由于ECOR設計中考慮了社交屬性與能量特性，進而比其他幾種協議取得更少的時延和跳數。

圖2 時延與信道數目的關系

圖3 跳數與信道數目的關系

從圖4中，我們可以看到隨著信道數目的增加，PDR也隨之增加，但是當增加到一定值時，其增加變得緩慢。這是因為信道數目更多，參與通信的機會就越大，數據傳輸也越快。CAODV的PDR值最小，ECOR和OSDRP的PDR值差不多，但是當信道數大時，ECOR的優勢更明顯。

圖4 包投遞率與信道數目的關系

2) SU數目對性能的影響。在本組實驗中，我們評估了SU數目對平均時延，跳數及包投遞率等性能的影響。信道數目為10。從圖5可以看到，隨著SU的增加，平均時延隨之降低，這是因為越多的SU參與通信，數據的傳輸進程將會加快。同時，我們也發現隨著SU數目的增加，ECOR的時延最小。

在圖6、圖7中，我們分析了SU數目對投遞率和跳數的影響。結果呈現：隨著SU數目的增加，投遞率和跳數明顯增加。由于受到PU通信的影響，當SU數目比較小時，所評估的兩項性能指標都比較低，這是因為此時數據傳輸的機會比較小。但是在所有的路由協議中，所提的ECOR具有更好的性能，這是因為在ECOR中，聯合考慮了網絡編碼技術并應用于數據傳輸過程中和基于社會屬性和能量的候選集選擇拍賣模型。

圖5 時延與SU數目的關系

圖6 跳數與SU數目的關系

圖7 包投遞率與SU數目的關系

3 結 語

針對認知社會物聯網數據傳輸問題，本文提出了一種新的能量感知的編碼機會路由ECOR。在ECOR中，證明了候選集的選擇是一個NP-hard問題，然后提出了一種基于社會屬性與能量的候選集拍賣模型，用以選擇更合適的節點傳輸數據。同時，在選擇候選集時考慮了信道分配問題，提出了一種基于博弈論的信道分配算法。另外，為了加快數據傳輸進程，我們采用網絡編碼技術，并對多種業務流提出一種新型的轉發優先級確定方法。最后通過仿真實驗驗證了所提機會路由在時延、包投遞率及跳數方面的優越性。由于在認知社會物聯網中存在大量異質的物聯設備，節點易受惡意節點的攻擊，下一步研究工作將引入信任管理及密碼學技術至安全路由設計中。