節(jié)點社會性下的無線網絡編碼傳輸分析

◎趙立新

（三門峽職業(yè)技術學院 信息傳媒學院，河南 三門峽 472000）

延遲容忍網絡可視為非連續(xù)性連接結構的網絡，源節(jié)點至目標節(jié)點之間無需完整的通道，借助移動節(jié)點具有的特質，選擇存儲—攜帶—轉發(fā)這一路由機制達成網絡通信目的。但是，即便DTN網絡的建設較為簡潔、快速，然而卻具有節(jié)點間反復移動與連接中斷促使通信鏈路難以繼續(xù)的問題，故而以往無線網絡與移動自組織網絡里面的路由機制難以引進到延遲容忍網絡中應用。因而，選取適宜的轉發(fā)節(jié)點讓數(shù)據(jù)能夠更好的轉發(fā)、投遞就變?yōu)榱薉TM網絡通信的重點。

1 NSNC-DTN網絡模型路由協(xié)議

1.1 NSNC-DTN模型

NSNC-DTN模型屬于將節(jié)點社會性為基礎選取轉發(fā)節(jié)點與應用RLNC轉發(fā)編譯好的數(shù)據(jù)包有效融合的DTN數(shù)據(jù)轉發(fā)路由。該模型具體包括兩部分：一是以節(jié)點社會性為基礎選取轉發(fā)節(jié)點的DTN網絡路由；二是引進RLNC。先針對DTN網絡里面的節(jié)點實施所屬社團的區(qū)分，借助社團發(fā)現(xiàn)算法將介數(shù)最大邊去掉以把DTN網絡區(qū)分成若干子社團。同時，針對社團之間的緊密度加以界定，以體現(xiàn)節(jié)點位于DTN網絡里面的活躍度，在NSNC-DTN模型里面，節(jié)點所處社團通過和其緊密度最佳的社團實施數(shù)據(jù)轉發(fā)，轉發(fā)節(jié)點選取最具活躍性的節(jié)點。并且，該模型里面引進RLNC，針對源節(jié)點實施RLNC，將相同目的節(jié)點信息統(tǒng)一編碼，以改善網絡吞吐量并縮減數(shù)據(jù)包轉發(fā)成本。此外，為深入改善網絡數(shù)據(jù)傳輸效率，將Center節(jié)點引進，對其數(shù)據(jù)包重新編碼、傳輸。NSNC-DTN網絡模型數(shù)據(jù)傳輸過程詳見下圖：

NSNC-DTN網絡模型數(shù)據(jù)轉發(fā)示意圖

經由圖1能得出，源節(jié)點與目的節(jié)點社團不同，前者和其他社團也未連邊，在此期間應用RLNC針對各位置一樣的數(shù)據(jù)包編碼，而后轉發(fā)傳輸編碼包。依照節(jié)點活躍程度選取適宜的相遇節(jié)點當做轉發(fā)節(jié)點，傳輸數(shù)據(jù)包前應對此節(jié)點紀要判定，假設為Center節(jié)點則把目的地一樣的數(shù)據(jù)包重新編碼傳送，若不是便直接發(fā)送數(shù)據(jù)包，由此直至目的節(jié)點取得完整信息或接收新編碼包獲取完整信息，經由泛洪機制促使所有轉發(fā)節(jié)點把轉發(fā)次數(shù)清零，并對緩存信息予以刪除。

為更好的認識NSNC-DTN網絡模型，特對相應概念加以闡述：社團，通過節(jié)點組成的集群結構，經由club符號顯示；節(jié)點間距離，表示節(jié)點和節(jié)點連接的最短距離；Center節(jié)點，數(shù)據(jù)發(fā)送期間，設置最適宜的節(jié)點活躍限值，在轉發(fā)節(jié)點比該數(shù)值大時，便被稱為Center節(jié)點。

并且，為對該模型更好的理解，還應進行如下假設：全部節(jié)點均享有相同的傳輸、緩存數(shù)據(jù)的功能；網絡中任意節(jié)點均有相應社團，一個社團僅囊括一個節(jié)點的現(xiàn)象能夠存在；社團和社團的緊密度具有差異性，能對其量化計算；節(jié)點位于全網里面的活躍程度具有差異性，所有節(jié)點均具備活躍度排名。

1.2 社團劃分

因網絡社團結構可確保數(shù)據(jù)傳送縮減網絡成本，故社團發(fā)現(xiàn)算法開始被大肆應用。以往社團結構劃分算法位于小型網絡結構里面具備較好效果，然而針對大型網絡結構來講收效甚微。就Radicchi算法而言，其屬于圖結構分析方式，主要經由對邊（i,j）的邊聚集系數(shù)計算以對節(jié)點i、j的近似度予以量化。邊的聚集系數(shù)C（i,j）具體借助了邊(i,j)的三角環(huán)占比，計算公式為：

C（i,j）——邊（i,j）聚合系數(shù)；Zi,j——囊括邊（i,j）的三角形數(shù)量；Ki——i的度；Kj——j的度。

Min（Ki-1，Kj-1）——節(jié)點與節(jié)點連邊最多可能屬于的三角形結構數(shù)

在某些節(jié)點同時隸屬較多社團期間，就構建產生了重疊社團結構。Radicchi算法對該結構難以實施節(jié)點社團劃分，故在此形勢下給予了改良之后的算法——LORadicchi算法。具體如下：

a.對網絡里面全部連邊聚集系數(shù)C（i,j）計算，并將最小邊去除。

b.對刪除邊兩大節(jié)點是否為多個社團予以判定，把同一時間隸屬較多社團的節(jié)點區(qū)分于某一社團里面。假設節(jié)點隸屬社團{cluba,clubb,clubc,...},則其和相應社團緊密度如下：

c.通過計算獲知可讓ct（i,cluba）值最大的社團，把節(jié)點i區(qū)分于該社團，將其他社團里面的節(jié)點i與相應連邊刪除。

d.針對沒有區(qū)分至社團的節(jié)點實施Radicchi算法，并對被重疊社團結構作用的節(jié)點邊聚系數(shù)重新計算，依照邊聚系數(shù)針對節(jié)點進行社團區(qū)分。

該算法以局部度量為主，具備較快計算速度。針對節(jié)點數(shù)顯示n、連變數(shù)顯示m的網絡，LORadicchi算法依照第一種方式對各連邊聚集系數(shù)時間復雜度o（m）計算。若社團數(shù)顯示s，那么步驟b、c復雜度即o(s)，最終需實施迭代針對局部連邊加以計算，復雜度o（m2/n2），故該算法時間復雜度即o（m+s+m2/n2）。

1.3 社團緊密度的計算

社團緊密度即社團與社團間數(shù)據(jù)包傳送頻繁度的大小，通過符號CTa,b代表。CTa,b大小通過如下因素確認，即社團a游走到社團b的概率及兩者間的平均距離。DTN網絡t時刻社團緊密度集合為

社團緊密度度量需思考局部隨機游走（LRW）的思想，即節(jié)點實施有限隨機游走，節(jié)點列可產生以概率為基礎的馬爾科夫鏈。同時，對兩大社團有限隨機游走后具有的連接概率予以計算。若無向DTN網絡G(V,E)的社團數(shù)顯示S，C表示網絡社團集合，則任意兩大社團a、b，用符號Pa,b顯示社團a接下來游走至社團b的概率，公式為：

計算公式如下：

ma,b表示社團a、社團b連接情況，鄰接矩陣M子元素之一。W即和社團a直接相連的社團個數(shù)，因DTN網絡為社團雙向連接網絡，故M為(w+1)*(w+1)對稱矩陣，通過la,b顯示社團a、b連邊數(shù)，那么

依照圖1，獲知cluba和其他社團連接狀態(tài)矩陣為

若數(shù)據(jù)包由 cluba通過 t步隨機游走至 clubb概率 ηa,b（t），那么

PT——概率矩陣轉置

同時，社團緊密度和社團間平均距離相關。若cluba、clubb各具備節(jié)點數(shù)na、nb，社則團a、b節(jié)點間最短距離為na*nb矩陣D（ca,cb）,那么兩者平均距離為

故cluba、clubbt時刻社團緊密度如下：

1.4 社團中節(jié)點活躍度計算

節(jié)點活躍度通過vitalityi顯示。DTN由節(jié)點轉發(fā)數(shù)據(jù)包頻率、外部社團連邊數(shù)、所連接社團數(shù)量化節(jié)點活躍度。通過G顯示DTN 各節(jié)點活躍度，如下

countiedges——節(jié)點i所在社團和外部社團連邊數(shù)，cli——節(jié)點i連接外部社團數(shù)，fri——節(jié)點i轉發(fā)數(shù)據(jù)包頻率

節(jié)點活躍度為：

α、β、λ均為可調節(jié)參數(shù)，α+β=1被滿足，能經由更改上述參數(shù)值變動節(jié)點連邊數(shù)、節(jié)點連接社團數(shù)的相對重要性。若DTN網絡具備n個節(jié)點，則各節(jié)點中心度時間復雜度o（n）。

1.5 網絡編碼

NSNC-DTN模型為RLNC，編碼過程具備源節(jié)點、Center節(jié)點編碼兩個過程。

a.源節(jié)點編碼。源節(jié)點形成n個相同位置數(shù)據(jù)包dp1,dp2,dp3,...dpn，對其執(zhí)行線性網絡編碼，獲知m 個編碼包 ec，m＞n，則

ek——有限域中的隨機系數(shù)，——編碼包頭部存儲編碼向量

其伴同編碼包同時發(fā)送，目的節(jié)點接收n個編碼向量線性無關編碼包期間，便能計算獲知原始發(fā)送n個數(shù)據(jù)包dp1,dp2,dp3,...dpn。

若編碼向量矩陣為

b.Center節(jié)點編碼。若Center節(jié)點與轉發(fā)節(jié)點j相遇，對兩者活躍度比較，若vitalityi＜vitalityj且vitalityi＜vitalityd，則將同一位置節(jié)點消息執(zhí)行線性編碼，且對編碼以后的數(shù)據(jù)包傳輸。

2 NSNC-DTN模型的數(shù)據(jù)轉發(fā)策略

NSNC-DTN模型轉發(fā)步驟如下：

a.針對節(jié)點實施初始設置，各節(jié)點對應一個線性動態(tài)鏈表，鏈表結構信息為（見下表）：

節(jié)點各做一次轉發(fā)節(jié)點，其transformi值加1；設定適宜的節(jié)點轉發(fā)次數(shù)閾值threshold,其間threshold∈（0，sum），sum即需轉發(fā)數(shù)據(jù)包數(shù)。對節(jié)點活躍度vitalityi閾值設置，為 maxVi，若Vitality1＞maxVi，那么該節(jié)點即Center節(jié)點。

鏈表結構信息表

b.節(jié)點社團劃分。對轉發(fā)、目的節(jié)點是不是為相同社團加以比對，若是便依照步驟f實施。c.對轉發(fā)節(jié)點外部連邊數(shù)是不是顯示0判定，若是依照步驟g實施。d.社團緊密度比較。如果transformi＞thresholod,便選取其他相同最大緊密度的節(jié)點為轉發(fā)節(jié)點，若轉發(fā)節(jié)點為Center節(jié)點，便重新進行隨機線性編碼，把其發(fā)送到節(jié)點j，若直接轉發(fā)，依照步驟b實施。e.節(jié)點活躍度比較。在前節(jié)點i和相遇節(jié)點j比較時，若NCAi＜NCAj，且后者比目的節(jié)點活躍度小，則節(jié)點i把數(shù)據(jù)包發(fā)送到節(jié)點j。f.判斷目的節(jié)點。對節(jié)點j與目的節(jié)點比較，若不相同，依照步驟e實施。g.執(zhí)行步驟f、c。h.對目的節(jié)點接收數(shù)據(jù)包是不是編碼包加以判定，若不是便直接發(fā)送數(shù)據(jù)，如若不然便需判定編碼包有無攜帶新信息，若有則把編碼包放置到編碼矩陣緩存，在編碼矩陣滿秩期間便能解碼，表示消息傳輸成功。

3 驗證結果

通過對NSNC-DTN網絡模型無線網絡編碼傳輸結果進行分析，來驗證該模型在無線網絡編程傳輸中的可行性和有效性。主要選取數(shù)據(jù)投送成功率、傳輸延遲和網絡緩存代價這三個核心的參數(shù)和維度來驗證NSNC-DTN網絡模型的性能，實驗結果如下：

NSNC-DTN網絡模型的數(shù)據(jù)投送成功率更高。相對于傳統(tǒng)的網絡模型，NSNC-DTN網絡模型的數(shù)據(jù)投送成功率提高了9%-18%，并且隨著網絡傳輸時間的推移，NSNC-DTN網絡模型的數(shù)據(jù)投送成功率與傳統(tǒng)方法相比優(yōu)勢會更大。

NSNC-DTN網絡模型端到端的網絡延遲更低。因為社團緊密度和節(jié)點活躍度計算重新計的引入，NSNC-DTN網絡模型中的每個節(jié)點都可能成為轉發(fā)節(jié)點，同時對每個節(jié)點的轉發(fā)次數(shù)做了閾值限制，這樣既有限地控制了緩存，并且可以對節(jié)點采取離線處理，最大程度上縮短了網絡傳輸延遲。

NSNC-DTN網絡模型的網絡緩存代價相對較小。因NSNC-DTN網絡模型僅僅保留一個數(shù)據(jù)包副本，因此網絡代價相對于其他方法會小很多，并且其他方法容易發(fā)送丟包情況，網絡緩存代價會隨著時間推移而一直增加。

4 結語

概括而言，DTN具體是對不具備連續(xù)性連接與節(jié)點資源具備實效性加以研究的一項網絡數(shù)據(jù)傳輸計劃，在軍事、航天通信、應急搶險等層面的消息交互上具備顯著效用。故而，此次研究依照DTN網絡特性，提出了新的以節(jié)點社會性為基礎的網絡模型，以對社團劃分算法予以優(yōu)化，經由社團緊密度與節(jié)點活躍程度的對此計算，選取適宜的轉發(fā)節(jié)點，與無線網絡編碼技術有效銜接實施數(shù)據(jù)傳輸。