嚴曄晴，陳志剛+，吳 嘉，王磊磊

1.中南大學 軟件學院，長沙 410075

2.“移動醫(yī)療”教育部-中國移動聯(lián)合實驗室，長沙 410083

1 概述

機會網(wǎng)絡(luò)是一種基于移動自組網(wǎng)[1]的延遲容忍網(wǎng)絡(luò)。在機會網(wǎng)絡(luò)中，由于節(jié)點的移動具有隨機性，節(jié)點之間不存在端到端的穩(wěn)定鏈路。在信息傳遞和數(shù)據(jù)轉(zhuǎn)發(fā)時，節(jié)點將需要被發(fā)送的信息存儲在自身緩存，再將信息轉(zhuǎn)發(fā)給相遇節(jié)點。信息通過節(jié)點的運動不斷地進行轉(zhuǎn)發(fā)，直到目的節(jié)點接收到數(shù)據(jù)信息時轉(zhuǎn)發(fā)過程結(jié)束。這種數(shù)據(jù)傳輸方式被稱作“存儲-攜帶-轉(zhuǎn)發(fā)”機制，是機會網(wǎng)絡(luò)中數(shù)據(jù)傳遞和路由選擇的基本原則[2-3]。由于通信路徑的不穩(wěn)定性，傳統(tǒng)的端到端的數(shù)據(jù)轉(zhuǎn)發(fā)機制在機會網(wǎng)絡(luò)中不再適用，怎樣在機會網(wǎng)絡(luò)中使用高效的路由算法成了目前面臨的最大挑戰(zhàn)[4]。

現(xiàn)今機會網(wǎng)絡(luò)的應用場景越來越多，主要適用于沒有固定基礎(chǔ)設(shè)施的惡劣環(huán)境下的網(wǎng)絡(luò)通信。由于貧富差距的存在，在偏遠地區(qū)經(jīng)常存在因網(wǎng)絡(luò)基礎(chǔ)設(shè)施不完善而不能接入互聯(lián)網(wǎng)的情形，而使用機會網(wǎng)絡(luò)技術(shù)能夠提供非即時，但價格低廉、相對可用的網(wǎng)絡(luò)服務。在不能覆蓋無線信號的大范圍區(qū)域內(nèi)進行的野生動物追蹤研究也是機會網(wǎng)絡(luò)應用的一個重要領(lǐng)域。在現(xiàn)代社會使用車輛出行是一種普遍現(xiàn)象，隨著配置無線智能設(shè)備的車輛不斷增多，行駛在道路上的車輛也可以進行無線短距離通信，從而可以構(gòu)成動態(tài)的、密度不均勻的、節(jié)點不定速移動的車載無線網(wǎng)絡(luò)，這種車載無線網(wǎng)絡(luò)也是機會網(wǎng)絡(luò)的一個重要應用場景。

機會網(wǎng)絡(luò)展示的是一種在不穩(wěn)定狀態(tài)下，通過節(jié)點移動帶來的接觸機會進行數(shù)據(jù)傳輸?shù)囊苿幼越M織網(wǎng)絡(luò)傳播方式[5]，也是基于“存儲-攜帶-轉(zhuǎn)發(fā)”策略的數(shù)據(jù)轉(zhuǎn)發(fā)模型。兩種簡單的路由選擇算法在機會網(wǎng)絡(luò)中開始普及使用。一種是Epidemic算法，是一種類似于疾病傳播的數(shù)據(jù)轉(zhuǎn)發(fā)機制，該算法中所有的節(jié)點簡單地將信息傳遞給所有相遇節(jié)點，具有較高的消息傳輸成功率，但網(wǎng)絡(luò)開銷也較大。另一種是Direct Transmission算法，與Epidemic算法不同的是采用Direct Transmission算法時，節(jié)點只有在遇到目的節(jié)點時才傳遞信息，其余情況時不傳遞信息。和其他算法相比Direct Transmission算法網(wǎng)絡(luò)開銷非常小，但是傳輸成功率低。

然而，隨著各種具有短距離通信功能的便攜式移動設(shè)備的迅速普及，平板電腦、手機、車載感知設(shè)備等終端被人類在日常生活中所攜帶,且處于不斷的運動之中。人們在社會生活中的活動不僅符合機會網(wǎng)絡(luò)節(jié)點隨機移動的特點[6]，而且出現(xiàn)了人類社會的某些社會特性。研究表明，節(jié)點間的社會關(guān)系對節(jié)點之間的相遇時間和持續(xù)時間具有重要的影響，可以提高網(wǎng)絡(luò)的消息傳輸成功率，并減小路由開銷[7]。然而，在這種應用場景內(nèi)，普通的機會網(wǎng)絡(luò)信息傳輸與數(shù)據(jù)轉(zhuǎn)發(fā)機制不再占有優(yōu)勢，基于社區(qū)和社會性的機會網(wǎng)絡(luò)算法更為適用和穩(wěn)定。

本文研究了節(jié)點間的社會關(guān)系，提出了一種融合社區(qū)和社會性的機會網(wǎng)絡(luò)有效數(shù)據(jù)轉(zhuǎn)發(fā)策略（a transmission data forwarding strategy integrating social relationships in opportunistic networks，EFIS）。本文在一定時間周期內(nèi)，對機會網(wǎng)絡(luò)中的節(jié)點進行社區(qū)劃分，利用網(wǎng)絡(luò)的社會性對社團結(jié)構(gòu)中的節(jié)點進行精簡，縮小網(wǎng)絡(luò)規(guī)模。實驗結(jié)果證明本文提出的這種算法可以準確地減少網(wǎng)絡(luò)中的低效或者無效節(jié)點，提高網(wǎng)絡(luò)傳輸效率，減小資源消耗。

本文貢獻如下：

（1）在機會網(wǎng)絡(luò)中，提出一種融合社區(qū)和社會性的數(shù)據(jù)轉(zhuǎn)發(fā)策略。將網(wǎng)絡(luò)劃分成社團之后，采用了一種方法來減少低效節(jié)點。

（2）在減少低效節(jié)點之后再次將社團結(jié)構(gòu)進行收縮，以保持社團的緊密性和數(shù)據(jù)傳遞的高效性。

（3）在保證傳輸成功率的同時，減少了無效節(jié)點的耗能，降低了網(wǎng)絡(luò)路由開銷。

本文的結(jié)構(gòu)劃分如下：在第2章中，描述并分析了機會網(wǎng)絡(luò)現(xiàn)有的研究成果和相關(guān)工作。在第3章中，提出了一種基于社區(qū)和社會性的數(shù)據(jù)轉(zhuǎn)發(fā)方法。仿真實驗的結(jié)果將在第4章給出。第5章對本文做的相關(guān)工作進行了總結(jié)。

2 相關(guān)工作

機會網(wǎng)絡(luò)路由作為實現(xiàn)間歇式通信環(huán)境下節(jié)點通信的理論基礎(chǔ)，具有十分重要的研究意義?；凇按鎯?攜帶-轉(zhuǎn)發(fā)”的數(shù)據(jù)轉(zhuǎn)發(fā)模式，現(xiàn)提出的多種數(shù)據(jù)轉(zhuǎn)發(fā)方式和路由算法的目標均致力于減小數(shù)據(jù)轉(zhuǎn)發(fā)造成的路由開銷和提高數(shù)據(jù)傳輸成功率。在機會網(wǎng)絡(luò)中，按照在數(shù)據(jù)轉(zhuǎn)發(fā)時是否需要額外的輔助信息，可以將目前的機會網(wǎng)絡(luò)路由算法分為直接型和輔助型。

直接型的機會網(wǎng)絡(luò)路由算法可以分為擴散傳播、被動等待、多拷貝三類。文獻[8]提出了一種類似疾病傳播的算法Epidemic算法。在Epidemic算法中，當兩個節(jié)點相遇時，通過交換對方所緩存數(shù)據(jù)包的ID，判斷對方節(jié)點具有哪些本節(jié)點所不具備的數(shù)據(jù)，并從對方節(jié)點獲得這些數(shù)據(jù)，得到兩個節(jié)點數(shù)據(jù)的一致。通過節(jié)點之間數(shù)據(jù)的兩兩交換，目的節(jié)點可以得到在它之前所有節(jié)點包含的信息。該算法在某些場景中具有很高的傳輸成功率，很小的傳輸延遲，但同時網(wǎng)絡(luò)負載大，算法適應性和可擴展性差。

文獻[9]提出了一種被動等待算法Direct Transmission，該算法是一種源節(jié)點直接等待的數(shù)據(jù)傳播機制。在數(shù)據(jù)傳輸過程中，源節(jié)點在沒有遇到目的節(jié)點之前一直將數(shù)據(jù)信息保存至自身緩存，直到遇到目的節(jié)點才進行轉(zhuǎn)發(fā)。Direct Transmission在現(xiàn)有的算法中，具有最低的網(wǎng)絡(luò)開銷，但同樣具有非常低的傳輸成功率。文獻[10]提出了一種多拷貝的路由算法Spray and Wait算法。Spray and Wait算法將信息的轉(zhuǎn)發(fā)分成兩個步驟：在Spray過程中，源節(jié)點將要傳遞的數(shù)據(jù)信息拷貝N次，將這些數(shù)據(jù)副本傳遞給不同的相遇節(jié)點，然后進入Wait過程。在傳輸過程中，當前節(jié)點不停地將數(shù)據(jù)信息轉(zhuǎn)發(fā)至相遇節(jié)點，直到目的節(jié)點接收到信息時算法才會停止。

輔助型的路由算法又根據(jù)在數(shù)據(jù)轉(zhuǎn)發(fā)策略設(shè)計時輔助信息的來源，將現(xiàn)存的一些路由算法進一步劃分為基于數(shù)據(jù)屬性、歷史接觸記錄、節(jié)點信息、節(jié)點社會地位四類。文獻[11]提出了一種基于數(shù)據(jù)屬性的機會網(wǎng)絡(luò)路由策略。在多個數(shù)據(jù)進行傳輸時，數(shù)據(jù)具有多種優(yōu)先級，使用優(yōu)先級執(zhí)行緩沖區(qū)管理可以改善機會網(wǎng)絡(luò)路由的性能。該算法提出可以根據(jù)數(shù)據(jù)屬性信息，給定一些數(shù)據(jù)的優(yōu)先級。在數(shù)據(jù)轉(zhuǎn)發(fā)時，節(jié)點比較緩存內(nèi)所存儲數(shù)據(jù)信息的優(yōu)先級，按優(yōu)先級高低順序依次進行存儲信息的轉(zhuǎn)發(fā)。文獻[12]利用節(jié)點的歷史接觸記錄，提出了一種基于節(jié)點概率的路由算法PRoPHET。當兩個節(jié)點相遇時，它們的接觸概率增加，否則隨著時間變長，接觸概率變小。PRoPHET算法通過節(jié)點交互的歷史記錄計算轉(zhuǎn)發(fā)概率并提出路由轉(zhuǎn)發(fā)的可能路徑，具有和Epidemic算法相差無幾的傳輸成功率，但是具有更低的路由開銷。

文獻[13]提出了一種基于社團結(jié)構(gòu)進行數(shù)據(jù)轉(zhuǎn)發(fā)的標簽策略算法Label算法。該算法利用了節(jié)點歷史紀錄中所屬社團結(jié)構(gòu)的信息為每個節(jié)點打上標簽，表明其所在社區(qū)的信息。節(jié)點在數(shù)據(jù)轉(zhuǎn)發(fā)過程中，只將消息傳遞給目的節(jié)點或者與目的節(jié)點相同標簽的其他節(jié)點。該算法操作簡便，但是傳輸時延大。文獻[14]提出了一種基于社區(qū)的轉(zhuǎn)發(fā)算法Bubble Rap。根據(jù)節(jié)點間交互信息的歷史紀錄可以得到節(jié)點的活躍度，該算法將所有節(jié)點按照活躍度進行排名，得到全局排名和在社區(qū)中的局部排名。在數(shù)據(jù)轉(zhuǎn)發(fā)時，節(jié)點按照全局排名依次將數(shù)據(jù)轉(zhuǎn)發(fā)給排名較高的節(jié)點，直到轉(zhuǎn)發(fā)給與目的節(jié)點處于同一社區(qū)的節(jié)點；再按照局部排名，在社區(qū)中進行數(shù)據(jù)轉(zhuǎn)發(fā)，直至目的節(jié)點收到數(shù)據(jù)信息。Bubble Rap算法采用單拷貝的策略，傳輸成功率較低，轉(zhuǎn)發(fā)延遲高。

文獻[15]提出了一種基于節(jié)點速度的移動機會網(wǎng)絡(luò)路由算法。這種算法在保證平均速度的同時研究速度多樣性對移動機會網(wǎng)絡(luò)的影響。節(jié)點速度多樣性意味著較長的平均通信時間，以及在持續(xù)的總通信時間內(nèi)通信的數(shù)量較少。這種算法通過調(diào)整節(jié)點速度多樣性可以提高網(wǎng)絡(luò)節(jié)點對資源的利用率，減少網(wǎng)絡(luò)開銷。文獻[16]提出了一種利用網(wǎng)絡(luò)編碼的數(shù)據(jù)轉(zhuǎn)發(fā)策略。這種算法利用一些能發(fā)現(xiàn)節(jié)點相遇可能性、包工具和編碼的機制，提高網(wǎng)絡(luò)的吞吐量。該算法的主要目標是在資源有限的條件下增加發(fā)現(xiàn)最佳路徑的可能性，通過精確的建模和評估方法提高路由算法的有效性。

本文提出了一種融合人社區(qū)和社會性的高效數(shù)據(jù)轉(zhuǎn)發(fā)策略，將機會網(wǎng)絡(luò)中的節(jié)點劃分成若干個社區(qū)結(jié)構(gòu)。社區(qū)劃分之后根據(jù)社區(qū)結(jié)構(gòu)中節(jié)點的特征刪除一部分低效節(jié)點，并進行社團結(jié)構(gòu)的再收縮。這種數(shù)據(jù)轉(zhuǎn)發(fā)方式將社區(qū)結(jié)構(gòu)進行了精簡，利用了社區(qū)內(nèi)部傳輸速度較快的特點，使數(shù)據(jù)轉(zhuǎn)發(fā)過程快速和高效，且相對穩(wěn)定和安全。

3 系統(tǒng)模型

3.1 社區(qū)劃分策略

機會網(wǎng)絡(luò)中，在一定時間范圍內(nèi)，網(wǎng)絡(luò)中節(jié)點的分布具有社會性，可以被劃分為不同的社區(qū)。本文周期性地對節(jié)點的連接狀態(tài)進行統(tǒng)計，按一定的時間間隔動態(tài)地劃分網(wǎng)絡(luò)的結(jié)構(gòu)。在實際網(wǎng)絡(luò)中并不存在絕對的彼此獨立的社團結(jié)構(gòu)，網(wǎng)絡(luò)由許多彼此重疊互相關(guān)聯(lián)的社團構(gòu)成[17]，并不能劃分為若干個相互分離的社區(qū)。若可以在一個網(wǎng)絡(luò)中縮減節(jié)點數(shù)量，減小網(wǎng)絡(luò)規(guī)模，就能得到連接更為緊密的網(wǎng)絡(luò)結(jié)構(gòu)。

一個社團可以看作由多個相互連通的“小的全耦合網(wǎng)絡(luò)”的集合，這些“全耦合網(wǎng)絡(luò)”稱為“派系”。在利用派系過濾算法進行社團劃分的時候，只要找到網(wǎng)絡(luò)中各部分最大的全耦合子圖，就可以利用該子圖來尋找派系的連通子圖，從而根據(jù)派系劃分將網(wǎng)絡(luò)劃分成許多個不重疊的社區(qū)。

定義1（全耦合網(wǎng)絡(luò)可能的初始大小N）網(wǎng)絡(luò)中可能存在的最大全耦合網(wǎng)絡(luò)的大小N。

定義2（全耦合網(wǎng)絡(luò)）若在一個網(wǎng)絡(luò)中每個節(jié)點到其他任意節(jié)點都存在路徑，則稱這個網(wǎng)絡(luò)為全耦合網(wǎng)絡(luò)。

定義3（重疊矩陣）類似于鄰接矩陣的結(jié)構(gòu)，矩陣的每一列對應一個派系，對角線上的值對應相應派系的規(guī)模，非對角線上元素代表兩個派系公共節(jié)點數(shù)。

已知網(wǎng)絡(luò)G=(V,E)，其中V={V1,V2,…,Vn}為節(jié)點集，表示n個節(jié)點的集合；設(shè)置一個可能的全耦合網(wǎng)絡(luò)的大小N。從某個節(jié)點Vi出發(fā)，找到所有包含節(jié)點Vi且大小為N的社團結(jié)構(gòu)后，刪除節(jié)點Vi及連接該節(jié)點的所有的邊。在找到所有大小為N的派系后，令N=N-1，不斷迭代直到N為2。至此，就找到了社團中所有的社團結(jié)構(gòu)。本文使用10個節(jié)點圖示說明基于派系過濾算法的社區(qū)劃分，這里設(shè)置N值為4。

使用派系過濾算法時，通常采用從大到小、迭代回歸的算法來尋找網(wǎng)絡(luò)中的派系。若一個頂點v和派系K所有的頂點都鄰接，則稱頂點v為派系K的鄰接頂點。若是派系的鄰接頂點與此派系的其他鄰接點不再鄰接，則稱此鄰接節(jié)點為第一類鄰接點；若是派系的鄰接頂點與派系的其他鄰接頂點有連接，則稱此鄰接頂點為第二類鄰接頂點。

對于一個初始節(jié)點Vi，設(shè)置一個包含所有兩兩相連的節(jié)點的集合A和一個與A中所有節(jié)點都相連的節(jié)點的集合B。集合B包含第一類鄰接節(jié)點和第二類鄰接節(jié)點。對節(jié)點Vi進行遍歷，初始集合A={Vi}，B=Neighbor[Vi]，從集合B中移出一個節(jié)點放置到集合A。檢查B中現(xiàn)存的所有元素是否仍然與A中所有節(jié)點相連，并刪除B中不再與A中所有節(jié)點均相連的節(jié)點。根據(jù)這種方式不斷地進行節(jié)點移動與刪除，以尋找網(wǎng)絡(luò)中的所有派系。在這個過程中，若A的大小未達到N之前B已經(jīng)為空，或A、B為一個之前遍歷時就已經(jīng)存在的派系的子集，則停止計算返回遞歸第一步，再尋找下一個初始節(jié)點進行迭代遍歷。反之，就得到一個新的派系，記錄該派系，然后返回遞歸第一步繼續(xù)尋找新的派系。本文采用如圖1所示的10節(jié)點網(wǎng)絡(luò)，圖示說明派系劃分的過程。

Fig.1 10-node network圖1 某10節(jié)點網(wǎng)絡(luò)結(jié)構(gòu)

在這個10節(jié)點的網(wǎng)絡(luò)結(jié)構(gòu)中，目標是將網(wǎng)絡(luò)劃分為派系為4的社團結(jié)構(gòu)。則假設(shè)初始節(jié)點V1，此時的集合B=Neighbor[V1]={V2,V3,V5,V6,V7}；若將節(jié)點V2移入集合A，集合B={V3,V5,V6,V7}，此時V3、V5、V6、V7與V1、V2均相連，不刪除任何節(jié)點；再將節(jié)點V3移入集合A，集合B中仍然與A中節(jié)點均連接的節(jié)點只剩下V5、V6。因為集合A的大小未達到N且集合B不為空，故仍然可以進行遍歷迭代。在遍歷節(jié)點V2時，存在一個與遍歷V1時相同的派系或派系的子集，此時該派系不保存。

找到了所有大小為設(shè)定全耦合網(wǎng)絡(luò)大小4的派系后，將設(shè)定的初始派系大小N減1，再次進行派系的迭代尋找，直至N為2時停止。這樣就得到了網(wǎng)絡(luò)中的所有全耦合網(wǎng)絡(luò)。

利用迭代回歸的思想，對網(wǎng)絡(luò)中所有節(jié)點進行遍歷，得到該網(wǎng)絡(luò)的6個派系如圖2所示。

Fig.2 Result of clique partition圖2 派系劃分結(jié)果

在找到網(wǎng)絡(luò)中這些所有的派系后，可以得到這些派系的重疊矩陣。其中，矩陣的每一列對應一個派系，對角線上的值對應相應派系大小，非對角線上元素代表兩個派系的公共節(jié)點數(shù)，如式（1）所示。

將派系重疊矩陣中對角線上小于N，而非對角線上小于N-1的元素置為0，其他元素置為1，就可以得到N派系社團結(jié)構(gòu)的鄰接矩陣式（2）。在這個矩陣中，各個連通部分代表各個N派系的社團。

根據(jù)式（2）的連通性分析，得到該網(wǎng)絡(luò)的兩個派系社團結(jié)構(gòu)如圖3所示。

Fig.3 Result of community partition圖3 網(wǎng)絡(luò)中的社團劃分結(jié)果

在網(wǎng)絡(luò)結(jié)構(gòu)中，采用如上的社區(qū)劃分策略可以將網(wǎng)絡(luò)劃分為若干個社團結(jié)構(gòu)。

3.2 社團結(jié)構(gòu)收縮策略

機會網(wǎng)絡(luò)是一種不存在端到端連接路徑的間歇性通信網(wǎng)絡(luò)，但由于節(jié)點的移動，可以帶來一定時間內(nèi)相對穩(wěn)定的通信機會。機會路由算法在進行信息傳輸與數(shù)據(jù)轉(zhuǎn)發(fā)時，最重要的原則是尋找到能夠?qū)⒛繕诵畔鬟_到目標節(jié)點的最佳路徑。在能夠保證最佳傳輸效率時，機會網(wǎng)絡(luò)作為一種特殊延遲容忍網(wǎng)絡(luò)，可以容忍適當?shù)膫鬏敃r延和消息丟棄。

由于機會網(wǎng)絡(luò)的信息傳播依賴于節(jié)點的運動，不同重要程度的節(jié)點對網(wǎng)絡(luò)中信息流的影響大不相同，因此衡量節(jié)點的重要程度顯得尤為重要[18]。若不對節(jié)點重要程度進行衡量，因為節(jié)點數(shù)目過多可能造成網(wǎng)絡(luò)擁塞，將大大降低傳輸成功率且造成無法容忍的時延。

在將網(wǎng)絡(luò)劃分為若干個社團之后，機會網(wǎng)絡(luò)中的節(jié)點從分散的節(jié)點結(jié)合成一個個的社團結(jié)構(gòu)，但在社團結(jié)構(gòu)中，各個節(jié)點的重要程度也有所差異。為了縮減社團結(jié)構(gòu)，可以計算每個節(jié)點刪除后網(wǎng)絡(luò)效率的變化來衡量節(jié)點在社團結(jié)構(gòu)中的重要程度。

對于具有S個節(jié)點的連通網(wǎng)絡(luò)，dij(i,j=1,2,…,S)表示網(wǎng)絡(luò)中節(jié)點Vi到節(jié)點Vj的最短距離，網(wǎng)絡(luò)的平均距離表示為：

但若網(wǎng)絡(luò)為非連通網(wǎng)絡(luò)，網(wǎng)絡(luò)的平均距離會成為無窮大。在這里引用網(wǎng)絡(luò)效率來衡量節(jié)點重要性，網(wǎng)絡(luò)的網(wǎng)絡(luò)效率表示為：

dii=0，在一個社團結(jié)構(gòu)中，若是刪除節(jié)點Vi后，網(wǎng)絡(luò)效率相對之前明顯發(fā)生變化，則說明網(wǎng)絡(luò)因為該節(jié)點產(chǎn)生了較大變化。在這里設(shè)置一個閾值衡量這個變化是否在可控范圍內(nèi)，若刪除節(jié)點之后網(wǎng)絡(luò)效率Kc變大且刪除節(jié)點Vi前后Kc值差的絕對值大于閾值T，則直接從社團網(wǎng)絡(luò)中刪除該節(jié)點。

刪除重要性不高的節(jié)點之后，社團結(jié)構(gòu)較之前發(fā)生變化，此時再次對社團結(jié)構(gòu)進行收縮以縮減網(wǎng)絡(luò)規(guī)模。節(jié)點的凝聚度是衡量網(wǎng)絡(luò)結(jié)構(gòu)是否可以收縮的重要指標，表示為：

由式（5）和式（6），凝聚度φ[G]可以表示為：

其中,S≥2,D表示一個網(wǎng)絡(luò)結(jié)構(gòu)中所有節(jié)點的距離合積，當網(wǎng)絡(luò)中只有一個節(jié)點時，φ[G]=1。G×Vi表示將節(jié)點Vi收縮得到的圖結(jié)構(gòu)，根據(jù)凝聚度可以算出節(jié)點在網(wǎng)絡(luò)中的重要程度：

由式（7）和式（8）可以得出：

其中,ki表示與節(jié)點Vi的鄰接節(jié)點的個數(shù)。計算出每個節(jié)點進行收縮后的重要度IM(vi)，若是進行收縮后的節(jié)點重要度IM(vi)大于控制參數(shù)ε，則用一個新的節(jié)點代替原本的節(jié)點及其所連的節(jié)點[19]。通過對社團結(jié)構(gòu)中節(jié)點的屬性進行分析，可以對社團結(jié)構(gòu)的大小進行縮減，將社團結(jié)構(gòu)進一步收縮，提高信息傳播和數(shù)據(jù)轉(zhuǎn)發(fā)的效率，偽代碼如下：

算法1結(jié)構(gòu)收縮策略

輸入：子圖Gn。

輸出：縮減后的子圖Gn′。

3.3 基于社會性的數(shù)據(jù)轉(zhuǎn)發(fā)策略

節(jié)點收縮之后，網(wǎng)絡(luò)規(guī)模減小，網(wǎng)絡(luò)結(jié)構(gòu)中的節(jié)點的社會性較強，在進行信息傳播和數(shù)據(jù)轉(zhuǎn)發(fā)時，通過社區(qū)進行轉(zhuǎn)發(fā)。對于網(wǎng)絡(luò)結(jié)構(gòu)中的N個社團結(jié)構(gòu)，通過對社會性的度量決定節(jié)點的轉(zhuǎn)發(fā)方式。

社會性定義為節(jié)點通過網(wǎng)絡(luò)到達其他節(jié)點的難易程度。社團結(jié)構(gòu)的社會性定義為其社團中所有節(jié)點的社會性的平均值。

起始節(jié)點在信息傳播與數(shù)據(jù)轉(zhuǎn)發(fā)時，將所攜帶的數(shù)據(jù)復制若干份，發(fā)送給本節(jié)點的所有鄰接節(jié)點，若鄰接節(jié)點處于某社團結(jié)構(gòu)，則將數(shù)據(jù)轉(zhuǎn)發(fā)至自身所在的社團結(jié)構(gòu)，否則傳播給自己的所有鄰接節(jié)點。

社區(qū)之間進行傳播時，計算每個社區(qū)的社會性，已經(jīng)得到數(shù)據(jù)副本的社團結(jié)構(gòu)對自己能夠到達的所有社區(qū)進行社會性的比較，將數(shù)據(jù)副本轉(zhuǎn)發(fā)至社會性比自身社會性要高的副本。目的節(jié)點得到數(shù)據(jù)副本時，轉(zhuǎn)發(fā)結(jié)束，發(fā)送反饋信息至起始節(jié)點。偽代碼如下：

算法2數(shù)據(jù)轉(zhuǎn)發(fā)機制

輸入：縮減后的子圖Gn′。

輸出：傳輸路徑。

3.4 算法優(yōu)勢及復雜度分析

當人類活動對網(wǎng)絡(luò)結(jié)構(gòu)產(chǎn)生影響時，移動節(jié)點的行為顯示出某些社會特性。越來越多的用戶利用具有短距離通信的便攜設(shè)備相互聯(lián)系和共享數(shù)據(jù)。在對機會網(wǎng)絡(luò)的最新研究中，上下文信息、節(jié)點興趣和節(jié)點社會屬性經(jīng)常被用作指標來度量機會網(wǎng)絡(luò)路由的性能。在機會社會網(wǎng)絡(luò)中，最大的問題是當大量的信息需要被轉(zhuǎn)發(fā)時，傳輸延遲和路由開銷極大。這是因為人們在數(shù)據(jù)傳輸過程中使用移動設(shè)備，而且周圍沒有合適的節(jié)點可以及時響應，最終導致傳輸延遲。許多現(xiàn)有的算法根據(jù)單個節(jié)點的社會特征進行路由選擇，并沒有考慮到機會網(wǎng)絡(luò)中的節(jié)點聚集現(xiàn)象與人類生活中的社區(qū)非常相似，利用社區(qū)的概念可以減少大量的傳輸延遲和路由開銷。

為了解決這些問題，該研究提出了一種融合社區(qū)和社會性的機會網(wǎng)絡(luò)有效數(shù)據(jù)轉(zhuǎn)發(fā)策略（EFIS）。由于單個節(jié)點的負載能力是有限的。本文采用基于社區(qū)的信息傳輸策略，因為通過社區(qū)進行的信息傳輸與數(shù)據(jù)轉(zhuǎn)發(fā)具有穩(wěn)定、高效且安全的特點，可以優(yōu)化機會網(wǎng)絡(luò)中的信息傳遞。

在本文算法中，采用派系的概念進行社區(qū)的劃分，解決了真實社會場景中的重疊社區(qū)問題。由于在社區(qū)劃分時單純地使用歷史社會連接屬性，會造成社區(qū)內(nèi)的節(jié)點重要程度差距迥異，故提出了一種社區(qū)結(jié)構(gòu)縮減的策略。對復雜網(wǎng)絡(luò)中多項節(jié)點重要程度指標進行了分析后，結(jié)合機會網(wǎng)絡(luò)負載能力較差，節(jié)點移動帶來的信息較少及傳輸不穩(wěn)定等特征，本文采用了網(wǎng)絡(luò)效率這一指標進行低效節(jié)點的刪減，并使用節(jié)點凝聚度的概念對社區(qū)結(jié)構(gòu)進行了再收縮。實驗證明這種社團縮減方式可以有效收縮社區(qū)結(jié)構(gòu)，使社區(qū)結(jié)構(gòu)緊密。

在這個算法中，EFIS算法的時間復雜度是O(n)。信息通過社區(qū)結(jié)構(gòu)進行傳輸，算法具有較高的傳輸速度及較高的傳輸效率。在Spray and Wait算法中，節(jié)點不斷地復制數(shù)據(jù)并將數(shù)據(jù)分配給它的鄰居，時間復雜度是O(n2)，PRoPHET算法的時間復雜度也是O(n2)。SCR（effective social relationship measurement and cluster based routing in mobile opportunistic networks）算法中節(jié)點通過社會關(guān)系進行選擇，形成一個本地聚類，算法復雜度為O(n)，但是與EFIS算法相比路由開銷較大。

4 仿真實驗與結(jié)果分析

4.1 仿真場景及算法參數(shù)

本文使用ONE[20]仿真模擬環(huán)境模擬持有移動通信設(shè)備的行人在真實城市步行的場景,實現(xiàn)EFIS算法的仿真并與Spray and Wait算法、ProPHET算法和SCR算法進行性能比較。仿真場景的參數(shù)具體設(shè)置如表1所示，EFIS算法模型參數(shù)的設(shè)定如表2所示。

本文比較了相同場景下不同的路由算法的性能與表現(xiàn)并且分析了參數(shù)對EFIS算法的影響。在本文中，將EFIS算法與Spray and Wait算法[10]、PRoPHET算法[12]以及SCR算法[21]進行了比較。前兩種算法是機會網(wǎng)絡(luò)路由研究中兩種經(jīng)典的算法，SCR算法是一種最新的算法，其基于社會關(guān)系進行集群路由的選擇。選用傳輸成功率、傳輸延遲、路由開銷[22]三個性能指標對算法進行性能分析。通過實驗表明，當N=14，t=0.15，ε=0.43時，EFIS算法性能綜合最優(yōu)。

Table 1 Simulation settings表1 仿真場景設(shè)置

Table 2 Parameter settings of algorithm表2 算法參數(shù)設(shè)置

4.2 實驗結(jié)果分析

4.2.1 社區(qū)劃分周期對消息傳輸成功率的影響

在社會聯(lián)系較為緊密的機會網(wǎng)絡(luò)中，應該采用融合社區(qū)和社會性的路由轉(zhuǎn)發(fā)策略，社區(qū)劃分周期對路由算法的影響十分重要。在一個周期內(nèi)，可以認為網(wǎng)絡(luò)中的節(jié)點狀態(tài)和社區(qū)結(jié)構(gòu)不發(fā)生改變，可以穩(wěn)定地進行數(shù)據(jù)傳播。如圖4所示，當選取的社區(qū)劃分周期較小時，由于社區(qū)結(jié)構(gòu)不夠穩(wěn)定，造成社區(qū)劃分對路由算法的指導效果不佳，傳輸成功率較低。隨著劃分周期增大，數(shù)據(jù)傳輸效率相應地提高。周期選取為900 s時，取得最佳傳輸成功率84%。隨著劃分周期繼續(xù)增大，傳輸成功率下降，2 700 s時，傳輸成功率是72%，算法性能較900 s時要差。這是因為社區(qū)劃分周期過長時，與實際情況不符。真實的節(jié)點分布狀態(tài)與假定的穩(wěn)定狀態(tài)不一致，之前的社區(qū)劃分結(jié)果不能很好地表示最新的社區(qū)結(jié)構(gòu)。

Fig.4 Influence of community partition cycle on packet delivery rate圖4 社區(qū)劃分周期對消息傳輸成功率的影響

4.2.2 節(jié)點緩存和節(jié)點數(shù)目對路由算法的影響

在進行仿真實驗時，將EFIS算法的性能與兩種傳統(tǒng)算法及一種最新算法進行比較。其中PRoPHET算法是基于概率的算法，Spray and Wait算法是基于多拷貝的算法，SCR是基于社會關(guān)系的聚集算法。

Spray and Wait算法、PRoPHET算法、SCR算法和EFIS算法在不同節(jié)點緩存大小和節(jié)點數(shù)目下對傳輸成功率的影響如圖5所示。在節(jié)點緩存較小，節(jié)點數(shù)目較少時，存在消息丟棄，路由算法的傳輸成功率較低。隨著節(jié)點緩存增大，節(jié)點數(shù)目增多，傳輸成功率相應提高。EFIS算法通過網(wǎng)絡(luò)中的社會性，將網(wǎng)絡(luò)中的節(jié)點劃分成社團，對社團結(jié)構(gòu)進行精簡，去除低效節(jié)點后再進行數(shù)據(jù)轉(zhuǎn)發(fā)。相對于Spray and Wait算法被動等待的特征，PRoPHET算法利用傳輸概率選擇性復制并轉(zhuǎn)發(fā)的策略，EFIS算法的傳輸成功率要更高。SCR算法是基于社會關(guān)系的算法，但是SCR算法中的本地聚類過程需要時間，在只能維持一段時間穩(wěn)定性的機會網(wǎng)絡(luò)中，消息傳輸成功率較EFIS算法差。

在Spray and Wait算法、PRoPHET算法、SCR算法和EFIS算法中，節(jié)點緩存和節(jié)點數(shù)目對于消息傳輸延遲的影響如圖6所示。隨著節(jié)點緩存增大，節(jié)點數(shù)目增多，算法的傳輸延遲增大。PRoPHET算法基于傳輸概率，在節(jié)點數(shù)目較多時需要進行大量運算，傳輸延遲最大。Spray and Wait算法進行多拷貝后，被動等待目的節(jié)點接收到消息，傳輸延遲也較大。SCR算法由于需要進行聚集過程，前期時延較大，隨著節(jié)點緩存變大，節(jié)點數(shù)目增多，傳輸時延較為改善，但仍然比EFIS算法要大。綜上所述，EFIS算法較其他三種算法傳輸時延較小。

Fig.5 Packet delivery ratio圖5 消息傳輸成功率

Fig.6 Transmission delay圖6 消息傳輸時延

Fig.7 Routing overhead圖7 路由開銷

在Spray and Wait算法、PRoPHET算法、SCR算法和EFIS算法中，節(jié)點緩存、節(jié)點數(shù)目對路由開銷的影響如圖7所示。Spray and Wait算法基于多拷貝，被動等待目的節(jié)點，路由開銷相對穩(wěn)定且較小。PRoPHET和EFIS算法隨著節(jié)點緩存增大，節(jié)點數(shù)目增多，路由開銷呈變小的趨勢。由于EFIS算法在社區(qū)劃分后，需要對結(jié)構(gòu)進行收縮需要一定的路由開銷，但與PROPHET算法需要不斷地計算傳輸效率相比較，路由開銷相對較小。SCR算法不僅需要分析節(jié)點的社會屬性，而且需要進行集聚，路由開銷較EFIS算法大。因此，相對其他三種算法，EFIS算法在具有社會聯(lián)系的機會網(wǎng)絡(luò)中路由開銷最小。

5 總結(jié)與展望

在機會網(wǎng)絡(luò)中，采用“存儲-攜帶-轉(zhuǎn)發(fā)”進行數(shù)據(jù)信息的轉(zhuǎn)發(fā)。隨著大量具有短距離通信功能的移動設(shè)備的出現(xiàn)，機會網(wǎng)絡(luò)呈現(xiàn)了非常強的社會性，節(jié)點間的社會關(guān)系對節(jié)點之間消息傳播具有重要影響，這些影響可以提高網(wǎng)絡(luò)的消息傳輸成功率，并減小路由開銷。在這種應用場景內(nèi)，普通的機會網(wǎng)絡(luò)信息傳輸與數(shù)據(jù)轉(zhuǎn)發(fā)機制不再占有優(yōu)勢。

本文提出了一種融合社區(qū)和社會性的機會網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)策略，通過派系過濾的思想對網(wǎng)絡(luò)中的節(jié)點進行社團劃分，根據(jù)節(jié)點對于網(wǎng)絡(luò)的影響判斷節(jié)點的重要性，刪除低效節(jié)點，并對社團再次進行結(jié)構(gòu)收縮。通過社會性，EFIS算法將數(shù)據(jù)轉(zhuǎn)發(fā)至社會性較高的節(jié)點和社區(qū)，具有較高的傳輸成功率和較低的傳輸延遲。

在未來的工作中，將根據(jù)更多的社交行為來改進本文的數(shù)據(jù)轉(zhuǎn)發(fā)算法，并研究機會社會路由中的安全性和隱私性。