王 超

(南陽理工學(xué)院 軟件學(xué)院，河南 南陽 473004)

移動社交網(wǎng)絡(luò)基于狀態(tài)的可重構(gòu)路由算法

王 超

(南陽理工學(xué)院 軟件學(xué)院，河南 南陽 473004)

隨著智能手機(jī)、移動終端設(shè)備的普及，通過移動設(shè)備來訪問社交網(wǎng)絡(luò)成為主流。為了提高移動社交網(wǎng)絡(luò)中信令傳遞的有效性和精準(zhǔn)性，文中提出了一種移動社交網(wǎng)絡(luò)中的可重構(gòu)容錯架構(gòu)和機(jī)理。它使用位權(quán)矩陣，基于最小開銷路徑算法來構(gòu)造連接兩個節(jié)點之間的路徑，并設(shè)計了一種網(wǎng)絡(luò)鏈接中斷時基于節(jié)點狀態(tài)識別的容錯路由算法，該算法使用故障識別矩陣和方向優(yōu)先權(quán)順序來選擇容錯路徑。通過對算法進(jìn)行理論分析和仿真實驗，結(jié)果表明該算法在架構(gòu)成功構(gòu)造率、物理鏈接使用率、網(wǎng)絡(luò)傳遞時延和數(shù)據(jù)報成功平均抵達(dá)率等方面具有優(yōu)越性，網(wǎng)絡(luò)構(gòu)造成功率和網(wǎng)絡(luò)資源利用率高，時延變化幅度小，數(shù)據(jù)傳遞可靠性高，更適合應(yīng)用于移動社交網(wǎng)絡(luò)場景。

移動社交網(wǎng)絡(luò)；可重構(gòu)；容錯；路由

0 引 言

近年來，傳統(tǒng)互聯(lián)網(wǎng)保持著飛速發(fā)展的勢頭，人們對互聯(lián)網(wǎng)特性和業(yè)務(wù)等方面的要求也越來越高，以IPv4為基礎(chǔ)的因特網(wǎng)面臨著嚴(yán)酷的挑戰(zhàn)，如路由可擴(kuò)展性差、服務(wù)質(zhì)量不高、移動網(wǎng)絡(luò)低效并存在安全隱患等問題。此外，隨著智能手機(jī)、平板電腦等移動設(shè)備的普及和傳感器技術(shù)的廣泛應(yīng)用，人們越來越熱衷于使用移動終端通過各種接入方式來訪問互聯(lián)網(wǎng)。基于此，以移動社交網(wǎng)絡(luò)(Mobile Social Network,MSN)為代表的下一代網(wǎng)絡(luò)應(yīng)運而生[1]。移動社交網(wǎng)絡(luò)的理論依據(jù)是美國哈弗大學(xué)教授米爾格拉姆創(chuàng)立的六度空間理論[2]，通過移動設(shè)備在虛擬的網(wǎng)絡(luò)空間里維系各自的人際關(guān)系，擴(kuò)大社交范圍。

路由技術(shù)是任何組網(wǎng)技術(shù)的關(guān)鍵問題。傳統(tǒng)互聯(lián)網(wǎng)的路由算法主要基于分組數(shù)據(jù)報在節(jié)點之間的跳數(shù)、延時、鏈接狀態(tài)等因素進(jìn)行設(shè)計，沒有考慮移動節(jié)點的資源有限性和用戶連接的間斷性。另外，移動社交網(wǎng)絡(luò)中用戶攜帶的移動終端之間具有特殊的社會關(guān)系，并且活動具有規(guī)律性，這是區(qū)別于其他移動網(wǎng)絡(luò)的本質(zhì)特征，如何有效利用社交網(wǎng)絡(luò)特性和用戶關(guān)系來提高信令傳遞的有效性成為了亟待解決的問題[3]。

1 相關(guān)研究

目前學(xué)術(shù)界和工業(yè)界對移動社會網(wǎng)絡(luò)的研究主要集中在社區(qū)檢測、路由算法、隱私和安全、中間件設(shè)計、應(yīng)用開發(fā)等相關(guān)領(lǐng)域。在路由算法研究中，Vahdat和Becker提出了EPidemic路由[4]，又稱為傳染式路由，節(jié)點之間的數(shù)據(jù)傳遞依賴于存儲轉(zhuǎn)發(fā)機(jī)制。該算法雖然在數(shù)據(jù)發(fā)送成功率和傳遞時延上有很大優(yōu)勢，但是卻犧牲了網(wǎng)絡(luò)中大量的帶寬資源和內(nèi)存資源。Lindgren等考慮了節(jié)點的有限資源問題并提出了一種概率性路由協(xié)議PROPHET[5]。該協(xié)議中，節(jié)點會收集相遇信息，每次與其他節(jié)點相遇都會更新傳遞數(shù)據(jù)的成功概率。該算法更適用于內(nèi)存不夠的節(jié)點網(wǎng)絡(luò)環(huán)境。Context-Aware Routing (CAR)[6]結(jié)合了同步傳遞和異步傳遞，可以基于歷史相遇信息預(yù)測出下一狀態(tài)的信息。Daly和Haahr利用社交網(wǎng)絡(luò)分析方法提出了一種路由算法SimBet[7]，它的理論基礎(chǔ)是小世界特性和Freeman提出的節(jié)點中心度理論，節(jié)點之間的相遇會交換介中心度和節(jié)點與目標(biāo)節(jié)點之間的相似度。XY路由算法運用在2D網(wǎng)格中，該算法為確定性算法，如果網(wǎng)絡(luò)正常，則無死鎖發(fā)生，一旦鏈接出現(xiàn)故障則會形成網(wǎng)絡(luò)堵塞，甚至使網(wǎng)絡(luò)癱瘓?；诠δ芄收夏Ｐ偷穆酚伤惴?Functional Fault model Based Routing algorithm,FFBR)根據(jù)當(dāng)前節(jié)點和目標(biāo)節(jié)點的坐標(biāo)以及附近節(jié)點的故障情況判別來進(jìn)行選路，而不需要存儲節(jié)點的狀態(tài)信息，但容易存在盲目轉(zhuǎn)發(fā)數(shù)據(jù)包的情況。

盡管很多學(xué)者對移動社交網(wǎng)絡(luò)中的路由算法進(jìn)行了設(shè)計研究，并取得了一定的成績，但是由于移動終端移動方位的不可預(yù)測性，可能產(chǎn)生節(jié)點鏈接中斷，進(jìn)而造成多種應(yīng)用程序服務(wù)停止，一方面給人們帶來了較差的用戶體會，另一方面使服務(wù)提供商蒙受利益損失。文獻(xiàn)[8]將鏈路中全部節(jié)點的平均強(qiáng)度最小化，使用開導(dǎo)式算法構(gòu)造邏輯承載網(wǎng)。其中考慮了負(fù)載均衡的自適應(yīng)虛擬網(wǎng)構(gòu)建算法(Balanced Adaptive virtual network Construction Algorithm,BACA),以網(wǎng)絡(luò)鏈接負(fù)載均衡和構(gòu)建代價最小為原則，同時對鏈接和節(jié)點進(jìn)行負(fù)載均衡，但是它沒有涉及資源迫切度，容易占用核心資源。文獻(xiàn)[9]則是采用事先計算備用鏈接，在出現(xiàn)鏈接中斷時將首選路徑的數(shù)據(jù)轉(zhuǎn)移到備用鏈接上，以此消除服務(wù)終止?；镜奶摂M網(wǎng)絡(luò)分配算法(Basic Virtual Network Assignment,Basic VNA)通過選擇輕量級的底層節(jié)點簇來實現(xiàn)鏈接和節(jié)點的負(fù)載均衡，但是由于采用了最短路徑算法，容易產(chǎn)生資源瓶頸。

這些研究要么只考慮怎樣優(yōu)化網(wǎng)絡(luò)資源，要么僅僅通過引入備用鏈接來解決鏈接中斷問題，代價太高。為此，文中提出了一種移動社交網(wǎng)絡(luò)中基于最小開銷路徑的可重構(gòu)容錯架構(gòu)和機(jī)理，以及在網(wǎng)絡(luò)鏈接中斷時基于節(jié)點狀態(tài)識別的容錯路由算法，以最小的重構(gòu)開銷來換取移動社交網(wǎng)絡(luò)的穩(wěn)定性。

2 可重構(gòu)容錯網(wǎng)絡(luò)架構(gòu)(Reconfigurable Fault-Tolerance Network Architecture,RFTNA)

無向圖UGs=(Ns,Ls,Bs)指的是基礎(chǔ)網(wǎng)絡(luò)，其中，Ns和Ls分別表示鏈接節(jié)點和鏈接組合；Bs表示基礎(chǔ)網(wǎng)絡(luò)可以負(fù)載的應(yīng)用服務(wù)水平。

無向圖UGv=(Nv,Lv,CRv)表示RFTNA的構(gòu)造要求，其中Nv和Lv表示客戶請求的RFTNA中虛擬節(jié)點和虛擬鏈接的組合，它們分別是Ns和Ls的子集；CRv指的是RFTNA構(gòu)造所需求的服務(wù)承載性能。

RFTNA構(gòu)造問題的陳述如下：一個滿足UGv中約束條件的UGv到UGs子集的映射，用UGDP表示為：

R:UGv→UGDP,UGDP=(NDP,EDP,CDP)

其中，NDP?Ns,EDP?Es，CDP表示構(gòu)造的RFTNA所具有的服務(wù)承載性能。

在陳述構(gòu)造算法前，引入下面的定義。

節(jié)點作用度：在網(wǎng)絡(luò)UGs中，設(shè)節(jié)點ki的度數(shù)為di，則向量NE=(1/d1,1/d2,…,1/dn)為節(jié)點對鄰接節(jié)點的作用度向量，稱為節(jié)點作用度[10]。

節(jié)點連接度：設(shè)R(UGs)為UGs的相鄰矩陣，那么向量NCF=NE*R(UGs)為每個節(jié)點對網(wǎng)絡(luò)連接性的作用程度，NCF(ki)的權(quán)值越大，節(jié)點連接度就越大。

NCF(ki)=

(1)

鏈接連接度：ECFi,j=(1/ki+1/kj)/2。

充實度：指的是當(dāng)節(jié)點或鏈接中斷時，性能損耗的RFTNA的數(shù)量。其中，EF(c)表示資源c的充實度，c可以是節(jié)點資源、鏈接資源；k表示資源c服務(wù)的RFTNA的個數(shù)；PMc表示資源c中已分配資源的百分比。

(2)

資源迫切度[11]：

(3)

其中，Ω(x)為x的資源迫切度；α和β是重構(gòu)因素，且α+β=1。Ω(x)值越大表示網(wǎng)絡(luò)對資源x的故障越敏感。

RFTNA構(gòu)造開銷函數(shù)：

(4)

其中，c(es)和c(ns)分別為構(gòu)造的RFTNA所占有的基礎(chǔ)鏈接和節(jié)點的初始開銷。節(jié)點迫切度越高，使用其資源構(gòu)造RFTNA花費的開銷就越大。

RFTNA構(gòu)造問題可以理解為找到相鄰兩個節(jié)點和這兩個節(jié)點之間的鏈接帶寬，用(m,n,k)表示，(m,n)表示相鄰的兩個節(jié)點，k代表鏈接帶寬要求，則(m,n,k)為RFTNA構(gòu)造單元。

RFTNA構(gòu)造問題可以理解為是在UGs中確定連接m和n的路徑，記為DPm,n，它滿足?k∈Ps,t,b(k)≥dk，其中b(k)指鏈接帶寬。對每個RFTNA構(gòu)造單元來講，會有多條符合條件的備用鏈接，那么根據(jù)構(gòu)造方法，要選擇構(gòu)造開銷最小的鏈接作為備用鏈接。

要獲取連接兩個節(jié)點m和n之間的開銷最小鏈接，需要UGs的位權(quán)矩陣WM(UGs)，接著使用最小路徑算法，得到最少開銷路徑。該最少開銷路徑算法(TheMinimumCostPathAlgorithm,TMCPA)流程如下：

輸入：UGs,UGz；

輸出：UGt。

(1)賦值UGt←空;

(2)將RFTNA構(gòu)造問題UGz劃分為，對每一個構(gòu)造單元(m,n,k)，循環(huán)執(zhí)行第(3)到第(5)步；

ωi,j=

(5)

(6)如果UGt!=空，返回輸出結(jié)果UGt；否則無法構(gòu)造RFTNA。

3 基于節(jié)點狀態(tài)識別的容錯路由算法(Fault-Tolerant Routing Algorithm Based on Node State Perception,FTRA-NSP)

在RFTNA中，使用故障識別矩陣[12]來標(biāo)記節(jié)點中斷，Y軸是節(jié)點輸入方向，X軸是節(jié)點輸出方向，對應(yīng)東、南、西、北四個方向。用0和1表示矩陣中各要素對應(yīng)的鏈接是否通暢，1表示鏈接無中斷，0表示鏈接存在中斷。

方向優(yōu)先權(quán)策略[13](DirectionPriority,DP)：假定數(shù)據(jù)報在進(jìn)入節(jié)點之后，會有四個方向選擇轉(zhuǎn)發(fā)。

將方向優(yōu)先權(quán)定義為DP1>DP2>DP3>DP4，數(shù)據(jù)報輸入方向為最低級DP4級，更靠近目標(biāo)節(jié)點的方向為最高級DP1級，垂直于更靠近目標(biāo)節(jié)點的方向為次高級DP2級，若DP1級和DP2級方向只有一個，那么剩下的方向為DP3級。

FTRA-NSP算法的流程如下：

(1)得到本地節(jié)點的方向優(yōu)先權(quán)順序。數(shù)據(jù)報到達(dá)本地節(jié)點后，首先計算出與目標(biāo)節(jié)點的偏移量Δx和Δy，然后與輸入方向一起確定本地節(jié)點的方向優(yōu)先權(quán)順序：{DP1,DP2,DP3,DP4}=DP(ID,Δx,Δy)。

(4)逐步降低本地節(jié)點方向級別及其對應(yīng)的鄰接節(jié)點并分別判斷，重復(fù)(2)、(3)步。

(5)選擇輸入方向DP4，返回上一層節(jié)點。如果以上各個方向都存在中斷無法通過，返回上一節(jié)點。

4 實驗結(jié)果

首先進(jìn)行的是算法復(fù)雜度分析[14]。在TMCPA算法中，假定Gp存在n個節(jié)點，Gr存在m個節(jié)點，那么RFTNA構(gòu)造過程的最壞時間復(fù)雜度為O(m2)。假定構(gòu)造單元有d個，更新每個單元位權(quán)矩陣的最壞時間復(fù)雜度為O(n2)，TMCDPA算法的最壞時間復(fù)雜度為O(m2+dn2)。算法中占用的存儲空間主要用來存儲構(gòu)造單元和最短路徑，所以空間復(fù)雜度為O(d+n)。

為了驗證文中提出的算法，采用NS-2仿真工具進(jìn)行仿真驗證，隨機(jī)生成物理網(wǎng)絡(luò)，節(jié)點的連通率為0.03，帶寬資源在60到80之間均勻分布。RFTNA構(gòu)造請求的傳遞過程服從時間單位為90，λr=6的泊松過程，鏈接中斷產(chǎn)生過程遵循強(qiáng)度為λf的泊松過程，鏈接中斷恢復(fù)時間取320個時間單位，每個RFTNA網(wǎng)絡(luò)的生存期服從θ=500的指數(shù)分布，數(shù)據(jù)報大小為8bit。比較TMCPA算法與BasicVNA、BACA算法在RFTNA成功構(gòu)造率和物理鏈接使用率等方面的差別，以及FTRA-NSP算法與XY、FFBR算法在網(wǎng)絡(luò)傳遞時延和數(shù)據(jù)報成功平均抵達(dá)率等方面的不同。

RFTNA成功構(gòu)造率是RFTNA構(gòu)造成功正常運行的個數(shù)占構(gòu)造請求總數(shù)的百分比，該參數(shù)的值越高說明構(gòu)造過程越成功并且容錯性能越好。

圖1 RFTNA平均成功構(gòu)造率

物理鏈接平均使用率是指構(gòu)造的RFTNA所占鏈接帶寬之和與基礎(chǔ)網(wǎng)絡(luò)全部鏈接帶寬之和的比值，它反映出網(wǎng)絡(luò)資源的有效利用率。

圖2是仿真運行時間為6 000時間單位的平均鏈接使用率結(jié)果。

圖2 RFTNA物理鏈接平均使用率

圖中所示，鏈接中斷率較低時，幾種算法的鏈接使用率基本相同，隨著鏈接中斷幾率的增大，BasicVNA和BACA下降幅度較大，TMCPA算法下降程度最小，這是因為它具有可重構(gòu)能力，并且考慮了資源迫切度。

圖3是XY、FFBR和FTRA-NSP算法在有故障情況下的平均傳遞時延對比。

圖3 平均傳遞時延比較

有故障時，XY路由算法具有最高的傳遞時延，F(xiàn)TRA-NSP和FFBR算法具有自適應(yīng)性，所以時延增加幅度小，但FTRA-NSP解決了FFBR隨意轉(zhuǎn)發(fā)數(shù)據(jù)報的問題，在網(wǎng)絡(luò)出現(xiàn)中斷時仍能根據(jù)節(jié)點狀態(tài)找到最優(yōu)的傳輸方向，其時延變化幅度最小。

圖4是XY、FFBR和FTRA-NSP算法在不同情況下的數(shù)據(jù)報成功平均抵達(dá)率。

在理想網(wǎng)絡(luò)中，各個算法都能保證數(shù)據(jù)報100%的抵達(dá)率，但隨著中斷比率的增大，XY算法成功抵達(dá)率下降最明顯，F(xiàn)FBR次之，F(xiàn)TRA-NSP算法的成功抵達(dá)率最高，這是因為該算法能夠感知節(jié)點狀態(tài)并確定優(yōu)先級大小，進(jìn)而選擇最優(yōu)路由進(jìn)行傳遞，保證了數(shù)據(jù)傳遞的高可靠性。

圖4 數(shù)據(jù)報成功平均抵達(dá)率

5 結(jié)束語

文中首先分析了移動社交網(wǎng)絡(luò)的研究現(xiàn)狀，然后提出了一種移動社交網(wǎng)絡(luò)中基于最小開銷路徑的可重構(gòu)容錯網(wǎng)絡(luò)模型和機(jī)制，以及在網(wǎng)絡(luò)鏈接中斷時基于節(jié)點狀態(tài)識別的容錯路由算法，以最小的重構(gòu)代價來換取移動社交網(wǎng)絡(luò)的可靠性，最后對算法的性能進(jìn)行了理論分析和實驗驗證。實驗結(jié)果表明，該方法在構(gòu)造成功率、物理鏈接平均使用率、網(wǎng)絡(luò)傳遞時延和數(shù)據(jù)報成功抵達(dá)率方面要優(yōu)于其他算法。下一步的研究方向主要集中在多節(jié)點發(fā)生故障時的恢復(fù)機(jī)制以及節(jié)點通信的負(fù)載均衡等方面。

[1]GENInetglobalenvironmentfornetworkinnovations[EB/OL].2009.http://www.geni.net/.

[2] 張 利，王 歡.我國當(dāng)前移動社交網(wǎng)絡(luò)用戶的基本特征[J].重慶郵電大學(xué)學(xué)報:社會科學(xué)版,2013,25(5):119-123.

[3] 段海夢.移動社交網(wǎng)絡(luò)中的情景感知與安全問題[J].中國電子商務(wù),2014(16)：65-65.

[4] 程永茂,徐 俊,曲 暉.基于mesh結(jié)構(gòu)的FHOFDM同步和信道估計算法[J].控制工程,2013,20(1):136-140.

[5]BulutE,GeyikSC,SzymanskiBK.Conditionalshortestpathroutingindelaytolerantnetworks[C]//ProcofIEEEinternationalsymposiumonaworldofwirelessmobileandmultimedianetworks.Montreal,Canada:IEEE,2010:1-6.

[6] 徐奕奕,唐培和,陳 陽.一種基于節(jié)點博弈的分層式數(shù)據(jù)網(wǎng)格資源調(diào)度優(yōu)化策略[J].控制工程,2014,21(6):925-929.

[7]DalyEM,HaahrM.Socialnetworkanalysisforroutingindisconnecteddelay-tolerantmanets[C]//Proceedingsofthe8thACMinternationalsymposiumonmobileadhocnetworkingandcomputing.[s.l.]:ACM,2007:32-40.

[8] 王浩學(xué)，汪斌強(qiáng)，于 婧,等．一體化承載網(wǎng)絡(luò)體系架構(gòu)研究[J]．計算機(jī)學(xué)報，2009，32(3)：371-376．

[9]RalhanM，IseamA，BoutabaR．Survivablevirtualnetworkembedding[C]//Proceedingsofthe9thinternationalnetworkingconference.Chennai，India:[s.n.]，2010：40-52．

[10] 齊 寧，王保進(jìn)，汪斌強(qiáng),等．均衡虛擬網(wǎng)構(gòu)建算法研究[J]．電子與信息學(xué)報，2011，33(6)：1301-1306．

[11] 曹懷虎,朱建明,潘 耘,等.情景感知的P2P移動社交網(wǎng)絡(luò)構(gòu)造及發(fā)現(xiàn)算法[J].計算機(jī)學(xué)報,2012,35(6)：1223-1234.

[12] 李 陟，李千目，張 宏,等.基于最近社交圈的社交時延容忍網(wǎng)絡(luò)路由策略[J].計算機(jī)研究與發(fā)展，2012,49(6)：1185-1195.

[13] 王 鵬,羅軍舟,李 偉,等.基于可信可控網(wǎng)絡(luò)的流量工程與覆蓋網(wǎng)路由的合作博弈模型[J].計算機(jī)學(xué)報，2010,33(9)：1663-1674.

[14] 王 恩，楊永健，趙衛(wèi)丹,等.容遲網(wǎng)絡(luò)中基于節(jié)點間親密度的分組路由方法[J].通信學(xué)報，2014,35(12):70-77.

Reconfigurable Routing Algorithm Based on State in Mobile Social Network

WANG Chao

(School of Software,Nanyang Institute of Technology,Nanyang 473004,China)

With the popularity of the smart phone and mobile terminal equipment,visiting the social network by using mobile devices has become mainstream.To improve the efficiency and accuracy of the message transmission in mobile social network,a reconfigurable fault tolerant architecture and mechanism was proposed,it uses position weight matrix and constructs path connecting two nodes based on the minimum cost path of mobile social network,it also designs a fault tolerant routing algorithm based on node state identification as soon as the network link interrupts.This algorithm uses fault identification matrix and direction priority order to select fault tolerant path.By theoretical analyzing and simulating,the result shows that the algorithm has many superiorities in the aspects of the architecture successful construction rate,the physical link utilization,network transmission delay and the average packet successful arrival rate,and it has high network construction ratio,high network utilization ratio,small delay variation and high data transmission reliability,which is more suitable for using in mobile social network scenario.

mobile social network;reconfigurable;fault-tolerant;routing

2015-04-13

2015-07-20

時間：2016-01-26

河南省基礎(chǔ)與前沿技術(shù)研究計劃項目(122300410258)作者簡介：王 超(1986-)，男，碩士，講師，CCF會員，研究方向為下一代網(wǎng)絡(luò)、軟件工程。

http://www.cnki.net/kcms/detail/61.1450.TP.20160126.1517.006.html

TP393

A

1673-629X(2016)02-0056-05

10.3969/j.issn.1673-629X.2016.02.013