移動社交網絡基于狀態的可重構路由算法

王 超

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

移動社交網絡基于狀態的可重構路由算法

王 超

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

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

移動社交網絡；可重構；容錯；路由

0 引 言

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

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

1 相關研究

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

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

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

2 可重構容錯網絡架構(Reconfigurable Fault-Tolerance Network Architecture,RFTNA)

無向圖UGs=(Ns,Ls,Bs)指的是基礎網絡，其中，Ns和Ls分別表示鏈接節點和鏈接組合；Bs表示基礎網絡可以負載的應用服務水平。

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

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

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

其中，NDP?Ns,EDP?Es，CDP表示構造的RFTNA所具有的服務承載性能。

在陳述構造算法前，引入下面的定義。

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

節點連接度：設R(UGs)為UGs的相鄰矩陣，那么向量NCF=NE*R(UGs)為每個節點對網絡連接性的作用程度，NCF(ki)的權值越大，節點連接度就越大。

NCF(ki)=

(1)

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

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

(2)

資源迫切度[11]：

(3)

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

RFTNA構造開銷函數：

(4)

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

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

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

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

輸入：UGs,UGz；

輸出：UGt。

(1)賦值UGt←空;

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

ωi,j=

(5)

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

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

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

方向優先權策略[13](DirectionPriority,DP)：假定數據報在進入節點之后，會有四個方向選擇轉發。

將方向優先權定義為DP1>DP2>DP3>DP4，數據報輸入方向為最低級DP4級，更靠近目標節點的方向為最高級DP1級，垂直于更靠近目標節點的方向為次高級DP2級，若DP1級和DP2級方向只有一個，那么剩下的方向為DP3級。

FTRA-NSP算法的流程如下：

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

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

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

4 實驗結果

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

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

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

圖1 RFTNA平均成功構造率

物理鏈接平均使用率是指構造的RFTNA所占鏈接帶寬之和與基礎網絡全部鏈接帶寬之和的比值，它反映出網絡資源的有效利用率。

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

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

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

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

圖3 平均傳遞時延比較

有故障時，XY路由算法具有最高的傳遞時延，FTRA-NSP和FFBR算法具有自適應性，所以時延增加幅度小，但FTRA-NSP解決了FFBR隨意轉發數據報的問題，在網絡出現中斷時仍能根據節點狀態找到最優的傳輸方向，其時延變化幅度最小。

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

在理想網絡中，各個算法都能保證數據報100%的抵達率，但隨著中斷比率的增大，XY算法成功抵達率下降最明顯，FFBR次之，FTRA-NSP算法的成功抵達率最高，這是因為該算法能夠感知節點狀態并確定優先級大小，進而選擇最優路由進行傳遞，保證了數據傳遞的高可靠性。

圖4 數據報成功平均抵達率

5 結束語

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

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

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

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

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

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

[6] 徐奕奕,唐培和,陳 陽.一種基于節點博弈的分層式數據網格資源調度優化策略[J].控制工程,2014,21(6):925-929.

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

[8] 王浩學，汪斌強，于 婧,等．一體化承載網絡體系架構研究[J]．計算機學報，2009，32(3)：371-376．

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

[10] 齊 寧，王保進，汪斌強,等．均衡虛擬網構建算法研究[J]．電子與信息學報，2011，33(6)：1301-1306．

[11] 曹懷虎,朱建明,潘 耘,等.情景感知的P2P移動社交網絡構造及發現算法[J].計算機學報,2012,35(6)：1223-1234.

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

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

[14] 王 恩，楊永健，趙衛丹,等.容遲網絡中基于節點間親密度的分組路由方法[J].通信學報，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

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

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