劉 輝，陳志剛，吳 嘉，王 丹，曾劍鋒

(1．中南大學(xué)軟件學(xué)院，湖南 長沙 410075；2．“移動醫(yī)療”教育部-中國移動聯(lián)合實(shí)驗(yàn)室，湖南 長沙 410083)

基于異或運(yùn)算的機(jī)會網(wǎng)絡(luò)高效轉(zhuǎn)發(fā)策略*

劉 輝1,2，陳志剛1,2，吳 嘉1,2，王 丹1,2，曾劍鋒1

(1．中南大學(xué)軟件學(xué)院，湖南 長沙 410075；2．“移動醫(yī)療”教育部-中國移動聯(lián)合實(shí)驗(yàn)室，湖南 長沙 410083)

通過對機(jī)會網(wǎng)絡(luò)中節(jié)點(diǎn)傳遞信息的方式進(jìn)行研究分析，遍歷可以通信的鄰居節(jié)點(diǎn)，將兩節(jié)點(diǎn)的信息作比較。通過交集的形式，選擇節(jié)點(diǎn)中攜帶信息異或程度最大的鄰居節(jié)點(diǎn)作為下一跳進(jìn)行信息傳遞，從而形成一條有效性最大的通信路徑?；谶@樣的分析過程，提出了一種基于異或運(yùn)算的機(jī)會網(wǎng)絡(luò)高效轉(zhuǎn)發(fā)策略FSXO。通過與機(jī)會網(wǎng)絡(luò)中的經(jīng)典算法對比，仿真結(jié)果表明，F(xiàn)SXO策略能夠在高傳輸成功率的情況下，減少網(wǎng)絡(luò)中無效數(shù)據(jù)副本的存在，從而有效地降低路由開銷，減少資源的消耗。

機(jī)會網(wǎng)絡(luò)；異或運(yùn)算；通信路徑；轉(zhuǎn)發(fā)策略

1 引言

機(jī)會網(wǎng)絡(luò)是不需要源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間存在完整鏈路，利用節(jié)點(diǎn)移動帶來的相遇機(jī)會實(shí)現(xiàn)通信的、時(shí)延和分裂可容忍的自組織網(wǎng)絡(luò)[1]。機(jī)會網(wǎng)絡(luò)來源于早期的延遲容忍網(wǎng)絡(luò)DTN(Delay Tolerant Network)[2]，機(jī)會網(wǎng)絡(luò)可以看成是具有一般DTN網(wǎng)絡(luò)特征的無線自組網(wǎng)。在機(jī)會網(wǎng)絡(luò)中，節(jié)點(diǎn)的位置不是固定的，網(wǎng)絡(luò)的規(guī)模也未進(jìn)行設(shè)置，源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的路徑事先不能確定是否存在。

機(jī)會網(wǎng)絡(luò)是利用節(jié)點(diǎn)移動而形成的通信機(jī)會逐跳進(jìn)行消息的傳輸，以“存儲—攜帶—轉(zhuǎn)發(fā)”的路由模式實(shí)現(xiàn)節(jié)點(diǎn)間的通信，由于其固有的特點(diǎn)能夠滿足某些特定應(yīng)用的需求[3]。目前，機(jī)會網(wǎng)絡(luò)的應(yīng)用主要在深太空信息網(wǎng)[4]、野外數(shù)據(jù)收集[5]和災(zāi)難場景應(yīng)用[6]等領(lǐng)域，取得了較好的成果。

2 相關(guān)工作

在機(jī)會網(wǎng)絡(luò)中，信息轉(zhuǎn)發(fā)是指信息由源節(jié)點(diǎn)經(jīng)過單跳或者多跳轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)的過程，如何有效地進(jìn)行信息轉(zhuǎn)發(fā)是機(jī)會網(wǎng)絡(luò)研究的一個(gè)熱點(diǎn)。

Direct Transmission算法[7]是基于轉(zhuǎn)發(fā)策略的路由算法，該算法的特點(diǎn)是數(shù)據(jù)分組在轉(zhuǎn)發(fā)過程中，節(jié)點(diǎn)不會對其進(jìn)行復(fù)制，只有源節(jié)點(diǎn)遇到目的節(jié)點(diǎn)時(shí)才會進(jìn)行數(shù)據(jù)分組轉(zhuǎn)發(fā)。因此，在整個(gè)網(wǎng)絡(luò)中不存在多余的數(shù)據(jù)副本，網(wǎng)絡(luò)路由開銷最小，但傳輸延遲較大，傳輸成功率不高。

Li Y等人在文獻(xiàn)[8]中提出了Epidemic算法，它的核心思想是當(dāng)兩個(gè)節(jié)點(diǎn)可以通信時(shí)，在獲知對方攜帶的數(shù)據(jù)分組情況后，僅傳送對方?jīng)]有的數(shù)據(jù)分組。理論上經(jīng)過多次交換后，每個(gè)非孤立節(jié)點(diǎn)都將獲得所有數(shù)據(jù)分組，從而實(shí)現(xiàn)數(shù)據(jù)傳輸。在網(wǎng)絡(luò)帶寬、節(jié)點(diǎn)緩存和節(jié)點(diǎn)能量等網(wǎng)絡(luò)資源豐富時(shí)，可以減少傳輸延遲，保證最大化數(shù)據(jù)傳輸?shù)某晒β?。然而在?shí)際應(yīng)用中，網(wǎng)絡(luò)資源是有限的，隨著節(jié)點(diǎn)數(shù)目的增多，網(wǎng)絡(luò)中會存在大量的無用數(shù)據(jù)副本，消耗過多的網(wǎng)絡(luò)資源，從而導(dǎo)致網(wǎng)絡(luò)性能下降。

Huang W等人在文獻(xiàn)[9]中提到，Spray and Wait算法分為Spray階段和Wait階段。在Spray階段，源節(jié)點(diǎn)的每個(gè)數(shù)據(jù)分組向網(wǎng)絡(luò)中注入一定數(shù)目的數(shù)據(jù)副本，并將其轉(zhuǎn)發(fā)給周圍節(jié)點(diǎn)。在Wait階段，如果數(shù)據(jù)在Spray階段沒有傳送到目標(biāo)節(jié)點(diǎn)，那么攜帶數(shù)據(jù)的節(jié)點(diǎn)將通過Direct Transmission方式把數(shù)據(jù)傳送到目標(biāo)節(jié)點(diǎn)。通過這種策略限定了網(wǎng)絡(luò)中的數(shù)據(jù)分組副本數(shù)量從而避免泛洪。該算法和其他路由算法綜合比較有明顯的優(yōu)勢。

PRoPHET算法[10]是基于概率計(jì)算策略的。當(dāng)兩個(gè)節(jié)點(diǎn)可以通信時(shí)，首先估算各自成功傳輸?shù)母怕?，利用該值來決定是否進(jìn)行數(shù)據(jù)分組轉(zhuǎn)發(fā)。在社區(qū)模型仿真場景中，該算法的性能較好。但是，在實(shí)際應(yīng)用中常常存在無法預(yù)測的問題，導(dǎo)致算法效率變低，影響該算法的效果。

通過對上述算法的研究分析，本文提出了一種基于異或運(yùn)算的機(jī)會網(wǎng)絡(luò)高效轉(zhuǎn)發(fā)策略FSXO(Forwarding Strategy based on XOR Operation)。在該算法下，相鄰節(jié)點(diǎn)間通過攜帶信息的比較，選擇節(jié)點(diǎn)中攜帶信息異或程度最大的鄰居節(jié)點(diǎn)作為下一跳進(jìn)行信息傳遞，從而形成一條有效性最大的通信路徑，從而更有可能將信息傳遞到其他通信區(qū)域，實(shí)現(xiàn)通信。

3 基于異或運(yùn)算的機(jī)會網(wǎng)絡(luò)高效轉(zhuǎn)發(fā)策略

3.1 機(jī)會網(wǎng)絡(luò)結(jié)構(gòu)

機(jī)會網(wǎng)絡(luò)的特點(diǎn)是節(jié)點(diǎn)只有在同一連通區(qū)域內(nèi)才可以相互傳遞信息，而不在同一連通區(qū)域的節(jié)點(diǎn)只有通過節(jié)點(diǎn)的移動才能實(shí)現(xiàn)信息的傳遞。在某個(gè)時(shí)段內(nèi)，整個(gè)網(wǎng)絡(luò)被劃分為多個(gè)連通域，機(jī)會網(wǎng)絡(luò)結(jié)構(gòu)圖如圖1所示。在灰色區(qū)域內(nèi)的節(jié)點(diǎn)可以相互通信，從而實(shí)現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)傳輸，但是不能將信息傳遞到整個(gè)網(wǎng)絡(luò)，只有通過活動節(jié)點(diǎn)的移動才能將本身攜帶的信息傳遞到其他區(qū)域。

由圖1可知，在T時(shí)間內(nèi)，A節(jié)點(diǎn)的數(shù)據(jù)只可以傳輸給D、E節(jié)點(diǎn)，而另一區(qū)域的B、C節(jié)點(diǎn)將無法獲得數(shù)據(jù)。只有通過A、D、E節(jié)點(diǎn)的移動，才有可能將數(shù)據(jù)傳遞到另外區(qū)域。因此，在某一連通區(qū)域如何選擇節(jié)點(diǎn)，使得節(jié)點(diǎn)攜帶的信息量更多，從而更有可能傳送到其他區(qū)域?qū)⑹潜疚牡闹饕芯抗ぷ鳌?/p>

Figure 1 Structure of opportunistic network圖1 機(jī)會網(wǎng)絡(luò)結(jié)構(gòu)圖

3.2 子網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

根據(jù)上述機(jī)會網(wǎng)絡(luò)特點(diǎn)，在網(wǎng)絡(luò)中任意選擇某一個(gè)子網(wǎng)絡(luò)作為研究的對象。在T時(shí)段，任選一個(gè)子網(wǎng)絡(luò)，假設(shè)該子網(wǎng)絡(luò)包含的節(jié)點(diǎn)集合為V={A,B,C,D,E,F,M,H,K,L}，所有參與的節(jié)點(diǎn)都為中繼節(jié)點(diǎn)，實(shí)現(xiàn)消息的轉(zhuǎn)發(fā)，子網(wǎng)絡(luò)節(jié)點(diǎn)圖如圖2所示。

假設(shè)當(dāng)前時(shí)段由A節(jié)點(diǎn)發(fā)送信息，并且信息傳遞速度大于節(jié)點(diǎn)移動速度，則當(dāng)前時(shí)段里子網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不發(fā)生變化，A節(jié)點(diǎn)的信息可以傳遞到子網(wǎng)絡(luò)的所有節(jié)點(diǎn)。根據(jù)節(jié)點(diǎn)和鄰接點(diǎn)的關(guān)系構(gòu)建當(dāng)前子網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)有向圖，如圖3所示。

Figure 2 Nodes of sub-network圖2 子網(wǎng)絡(luò)節(jié)點(diǎn)圖

Figure 3 Topology structure of sub-network圖3 子網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，我們得到有向圖G=(V，E)，其中V={A,B,C,D,E,F,M,H,K,L}，E={〈A，B〉，〈A，C〉，〈A，D〉，〈B，E〉，〈B，F(xiàn)〉，〈C，M〉，〈D，H〉，〈F，K〉，〈F，L〉}。通過有向圖可以看到可能的信息傳遞路徑。此時(shí)，需要找的是一條有效性最大的通信路徑，將它作為最終的信息傳遞路徑，使得信息經(jīng)過多跳傳遞后的終節(jié)點(diǎn)攜帶的信息量最大，從而更有可能將信息傳遞出去，實(shí)現(xiàn)通信。

3.3 節(jié)點(diǎn)信息遍歷過程

每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)緩沖區(qū)，緩沖區(qū)中存放本節(jié)點(diǎn)和其他節(jié)點(diǎn)需要本節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)分組，每個(gè)數(shù)據(jù)分組有一個(gè)全局唯一的標(biāo)識。令節(jié)點(diǎn)集合V中的每個(gè)節(jié)點(diǎn)數(shù)據(jù)分組分別為DA={a，b}，DB={c，d，e}，DC={f，g}，DD={a，c}，DE={x，y}，DF={h，i}，DM={a，x}，DH={x，y，z}，DK={j，k，l，m}，DL={p，q，y}。添加了數(shù)據(jù)分組的子網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)有向圖如圖4所示。

Figure 4 Topology structure of sub-network with data圖4 子網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)有向圖(帶數(shù)據(jù))

為了獲得最優(yōu)化路徑節(jié)點(diǎn)集合，令集合V中每個(gè)節(jié)點(diǎn)各自形成一個(gè)只含本身節(jié)點(diǎn)的子集合，記作VA={A}，VB={B}，VC={C}，VD={D}，VE={E}，VF={F}，VM={M}，VH={H}，VK={K}，VL={L}。為了確定最優(yōu)路徑，將采用廣度優(yōu)先搜索(BFS)遍歷有向圖G中的節(jié)點(diǎn)。

基于圖4的算法具體執(zhí)行過程如下：

(1)初始時(shí)，Queue隊(duì)列只有A節(jié)點(diǎn)一個(gè)元素，將該元素出隊(duì)列，即A節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)，訪問A節(jié)點(diǎn)的第一個(gè)鄰接點(diǎn)B，此時(shí)VA中只有A一個(gè)元素，作如下運(yùn)算：

IntersectionAB=DA∩DB

IntersectionAB集合為空，則表明當(dāng)前兩個(gè)節(jié)點(diǎn)所攜帶的信息是不一樣的，將B節(jié)點(diǎn)插入到Queue隊(duì)列中，并將VA中的元素加入到VB中。

(2)繼續(xù)訪問A節(jié)點(diǎn)的下一個(gè)鄰接點(diǎn)C，作如下運(yùn)算：

IntersectionAC=DA∩DC

IntersectionAC集合也為空，將C節(jié)點(diǎn)插入到Queue隊(duì)列中，并將VA中的元素加入到VC中。

(3)繼續(xù)訪問A節(jié)點(diǎn)的下一個(gè)鄰接點(diǎn)D，作如下運(yùn)算：

IntersectionAD=DA∩DD

IntersectionAD集合不為空，則表明信息存在冗余，不執(zhí)行其他操作。

(4)當(dāng)前節(jié)點(diǎn)A沒有鄰接點(diǎn)，則將Queue隊(duì)列隊(duì)首元素B出隊(duì)列，訪問節(jié)點(diǎn)B的鄰接點(diǎn)E，VB中此時(shí)有兩個(gè)元素A和B，作如下運(yùn)算：

IntersectionABE= DA∩DB∩DE

IntersectionABE集合為空，將E節(jié)點(diǎn)插入到Queue隊(duì)列中，并將VB中的元素加入到VE中。

(5)繼續(xù)訪問B節(jié)點(diǎn)的下一個(gè)鄰接點(diǎn)F，作如下運(yùn)算：

IntersectionABF= DA∩DB∩DF

IntersectionABF集合為空，將F節(jié)點(diǎn)插入到Queue隊(duì)列中，并將VB中的元素加入到VF中。

(6)當(dāng)前節(jié)點(diǎn)B沒有鄰接點(diǎn)，則將Queue隊(duì)列隊(duì)首元素C出隊(duì)列，訪問節(jié)點(diǎn)C的鄰接點(diǎn)M，VC中此時(shí)有兩個(gè)元素A和C，作如下運(yùn)算：

IntersectionACM= DA∩DC∩DM

IntersectionACM集合不為空，則不執(zhí)行其他操作。

(7)當(dāng)前節(jié)點(diǎn)C沒有鄰接點(diǎn)，則將Queue隊(duì)列隊(duì)首元素E出隊(duì)列，E節(jié)點(diǎn)沒有鄰接點(diǎn)，繼續(xù)將Queue隊(duì)列隊(duì)首元素F出隊(duì)列，訪問節(jié)點(diǎn)F的鄰接點(diǎn)K，VF中此時(shí)有三個(gè)元素A、B和F，作如下運(yùn)算：

IntersectionABFK=DA∩DB∩DF∩DK

IntersectionABFK集合為空，將K節(jié)點(diǎn)插入到Queue隊(duì)列中，并將VF中的元素加入到VK中。

(8)繼續(xù)訪問F節(jié)點(diǎn)的下一個(gè)鄰接點(diǎn)L，作如下運(yùn)算：

IntersectionABFL=DA∩DB∩DF∩DL

IntersectionABFL集合為空，將L節(jié)點(diǎn)插入到Queue隊(duì)列中，并將VF中的元素加入到VL中。

(9)當(dāng)前節(jié)點(diǎn)F沒有鄰接點(diǎn)，則將Queue隊(duì)列隊(duì)首元素K出隊(duì)列，K節(jié)點(diǎn)沒有鄰接點(diǎn)，繼續(xù)將Queue隊(duì)列隊(duì)首元素L出隊(duì)列，L節(jié)點(diǎn)也沒有鄰接點(diǎn)，此時(shí)Queue隊(duì)列為空，訪問結(jié)束。

(10)統(tǒng)計(jì)節(jié)點(diǎn)個(gè)數(shù)不為1的集合的信息量，知VK集合中有A、B、F、K四個(gè)元素，其元素對應(yīng)的數(shù)據(jù)分組集合信息量總和最大，將ABFK設(shè)為最優(yōu)，消息通過復(fù)制策略在路徑A→B→F→K進(jìn)行傳遞。

3.4 算法設(shè)計(jì)

根據(jù)前一節(jié)的遍歷過程可知FSXO算法執(zhí)行過程如下：

(1)隊(duì)列Queue初始值存放發(fā)送信息的第一個(gè)節(jié)點(diǎn)，將隊(duì)首元素出隊(duì)列作為當(dāng)前節(jié)點(diǎn)i。

(2)根據(jù)BFS訪問當(dāng)前節(jié)點(diǎn)i的鄰接點(diǎn)j，將Dj與Vi集合中的所有元素對應(yīng)的數(shù)據(jù)分組集合同時(shí)做交操作，即如下運(yùn)算：

Intersectionij=Dj∩Di1∩…∩Din

(1)

其中，n為Vi集合的元素個(gè)數(shù)，Di1到Din為Vi集合元素對應(yīng)的數(shù)據(jù)分組集合。

(3)如果Intersectionij集合為空，則將節(jié)點(diǎn)j插入到Queue隊(duì)列尾部，并將節(jié)點(diǎn)i對應(yīng)的Vi集合的所有元素加入到Vj中，否則不執(zhí)行任何操作，轉(zhuǎn)到(4)。

(4)繼續(xù)訪問當(dāng)前節(jié)點(diǎn)i其他鄰接點(diǎn)，重復(fù)(2)和(3)，直到其所有鄰接點(diǎn)訪問完畢。

(5)將隊(duì)列的隊(duì)首節(jié)點(diǎn)出隊(duì)列，作為當(dāng)前節(jié)點(diǎn)i，重復(fù)(2)、(3)、(4)，直至隊(duì)列為空。

(6)統(tǒng)計(jì)節(jié)點(diǎn)個(gè)數(shù)不為1的集合的信息量，信息量最大的集合則為最優(yōu)路徑的節(jié)點(diǎn)集合，從而確定信息傳遞路徑，將消息通過復(fù)制策略在該路徑上傳遞。

根據(jù)上述選擇的過程，可以得到基于異或運(yùn)算的機(jī)會網(wǎng)絡(luò)高效路由算法，如下所示。

算法1AnEfficientForwardingStrategybasedonXOROperation

1:Input:AgraphG(V,E),asourceS, Dα:thecorrelativeinformationcollectionofα(α∈ V);

2:Output:Apathofthemaximuminformation。

3:Init:InitQueue(Q),Vi/*eachelementofVasanodecollection*/

4:Set:EnQueue(Q,S);

5:while(!QueueEmpty(Q))

6:DeQueue(Q,β);

7:for(k=FirstAdjVex(G,β);k>=0;k=NextAdjVex(G,β,k))

8:nis the number of element ofVβ,Dα1,…,Dαnare the correlativeinformation collection of element ofVβ;

9:IntersectionβK=DK∩Dα1∩…∩Dαn;

10:if(IntersectionβK=?)

11:EnQueue(Q,k);

12:add all element ofVβto the collectionVK;

13:end if; end for; end while

14:select a maximum information collection ofVithat the number of elements inViis greater than one;

15:according to the above collection generate a path;

通過上述的選擇操作，可以避免網(wǎng)絡(luò)中存在大量的數(shù)據(jù)分組副本，從而避免消耗大量的網(wǎng)絡(luò)資源。

4 實(shí)驗(yàn)仿真與結(jié)果分析

本文將采用ONE(Opportunistic Networking Environment)[11]仿真工具,并與經(jīng)典的Epidemic算法和PRoPHET算法在仿真平臺上進(jìn)行比較。將選用傳輸成功率、傳輸延遲和路由開銷這三個(gè)指標(biāo)對算法進(jìn)行比較分析。仿真場景設(shè)置如表1所示。

Table 1 Parameters of simulation表1 仿真場景的參數(shù)

下面是Epidemic算法、PRoPHET算法和FSXO算法在不同節(jié)點(diǎn)密度下的表現(xiàn)。圖5為不同節(jié)點(diǎn)密度下三種算法傳輸成功率的實(shí)驗(yàn)結(jié)果。

Figure 5 Delivery ratio圖5 傳輸成功率

由圖5可知，節(jié)點(diǎn)密度對算法傳輸成功率有較大的影響。在節(jié)點(diǎn)較少的情況下，三種算法的傳輸成功率差不多。隨著節(jié)點(diǎn)數(shù)目的增加，各個(gè)算法的傳輸成功率都有所增加，但是FSXO算法增加幅度比其他兩種算法的高。在節(jié)點(diǎn)數(shù)量到達(dá)400時(shí)，Epidemic算法和PRoPHET算法的傳輸成功率保持在40%左右，而FSXO算法的傳輸成功率卻可以達(dá)到70%左右，其根本原因在于FSXO算法構(gòu)建網(wǎng)絡(luò)拓?fù)鋱D，通過異或操作選擇出了一條信息量大的通信路徑進(jìn)行信息傳遞。正是這種有選擇性的信息傳遞使得其在仿真平臺下能夠取得較高的信息傳輸成功率。

節(jié)點(diǎn)數(shù)量對傳輸延遲的影響如圖6所示。由圖6可知，節(jié)點(diǎn)數(shù)量對三種算法的傳輸延遲影響都不大。Epidemic算法的傳輸延遲要優(yōu)于FSXO算法和PRoPHET算法，這是因?yàn)镋pidemic算法本質(zhì)上是一種洪泛算法，它能夠減少傳輸延遲，而其它兩種算法是基于某種選擇性的算法，使得一些節(jié)點(diǎn)不能參與通信而造成延遲。在節(jié)點(diǎn)數(shù)量較少時(shí)，PRoPHET算法增加的趨勢比FSXO算法明顯。隨著節(jié)點(diǎn)數(shù)量增加，F(xiàn)SXO算法和PRoPHET算法的傳輸延遲非常接近。從仿真結(jié)果得出，Epidemic算法的延遲時(shí)間小于FSXO算法和PRoPHET算法的。

Figure 6 Delivery delay圖6 傳輸延遲

節(jié)點(diǎn)數(shù)量對路由開銷的影響如圖7所示。在節(jié)點(diǎn)個(gè)數(shù)較少的情況下，三種算法的路由開銷差不多。Epidemic算法的路由開銷隨著節(jié)點(diǎn)數(shù)量的增加而大幅度增加，增加趨勢非常明顯，說明該算法隨著節(jié)點(diǎn)數(shù)量的增加網(wǎng)絡(luò)中存在大量的數(shù)據(jù)分組副本，浪費(fèi)網(wǎng)絡(luò)資源。PRoPHET算法的路由開銷也隨著節(jié)點(diǎn)的數(shù)量增加而增加，但是增加的幅度比Epidemic算法小。就路由開銷而言，PRoPHET算法要優(yōu)于Epidemic算法。FSXO算法的性能明顯優(yōu)于前面兩種算法，在節(jié)點(diǎn)個(gè)數(shù)達(dá)到400時(shí)，F(xiàn)SXO算法的路由開銷還不到Epidemic算法的1/2，比PRoPHET算法也要少1/3。這是由于該算法不是將信息轉(zhuǎn)發(fā)給所有遇到的節(jié)點(diǎn)，而是通過異或運(yùn)算有選擇地選擇了有效性高的一串節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，從而減少網(wǎng)絡(luò)中副本的存在。仿真結(jié)果表明，F(xiàn)SXO算法能夠減少路由開銷，節(jié)約網(wǎng)絡(luò)資源。

Figure 7 Overhead圖7 路由開銷

通過對仿真實(shí)驗(yàn)結(jié)果的分析可知，F(xiàn)SXO算法能在減少路由開銷的同時(shí)保證較高水平的傳輸成功率，減少網(wǎng)絡(luò)中數(shù)據(jù)分組副本的數(shù)量，進(jìn)而節(jié)約網(wǎng)絡(luò)資源，提高網(wǎng)絡(luò)的整體性能水平。不足之處在于FSXO算法會造成一定的傳輸延遲，但就整體性能而言，F(xiàn)SXO算法相對于Epidemic算法和PRoPHET算法有較大的進(jìn)步。

5 結(jié)束語

針對機(jī)會網(wǎng)絡(luò)中節(jié)點(diǎn)傳遞信息的特點(diǎn)，本文提出了基于信息異或的選擇信息量最大的路徑傳遞信息的算法FSXO。通過遍歷可通信的鄰居節(jié)點(diǎn)，將兩節(jié)點(diǎn)的信息作比較。通過交集的形式，比較節(jié)點(diǎn)中攜帶信息異或程度最大的鄰居節(jié)點(diǎn)作為下一跳進(jìn)行信息傳遞，從而形成一條有效性最大的通信路徑。通過與機(jī)會網(wǎng)絡(luò)中經(jīng)典的Epidemic算法和PRoPHET算法對比，仿真結(jié)果表明，F(xiàn)SXO算法能夠在高傳輸成功率的情況下，減少網(wǎng)絡(luò)中無效數(shù)據(jù)副本的存在，從而有效降低路由開銷，這種特性使得該算法非常適合于能量資源較少的場景。

[1] Xiong Yong-ping, Sun Li-min, Niu Jian-wei, et al.Opportunistic networks[J].Journal of Software, 2009, 20 (1):124-137.(in Chinese)

[2] Jacquet P, Mans B, Rodolakis G. Information propagation speed in mobile and delay tolerant networks[J]. IEEE Transactions on Information Theory, 2010, 56(10):5001-5015.

[3] Hu Si-quan, Wang Hong-bing, Wang Jun-feng. Research on the opportunistic networks [J]. Computer Science, 2009, 36 (10):32-37.(in Chinese)

[4] Zhang L, Huang W, Miao X, et al. The impact of storage capacity usage and predictable contact schedule on dynamic routing for opportunistic deep space information networks[J]. Wireless Personal Communications, 2014,77(2):1-19.

[5] Tseng Y C, Wu F J, Lai W T. Opportunistic data collection for disconnected wireless sensor networks by mobile mules[J]. Ad Hoc Networks, 2013, 11(3):1150-1164.

[6] Martín-Campillo A, Crowcroft J, Yoneki E, et al. Evaluating opportunistic networks in disaster scenarios[J]. Journal of Network and Computer Applications, 2013, 36(2):870-880.

[7] Sun Jian-zhi, Liu Nai-rui, Zhang Ying-xin, et al.Performance analysis of typical routing algorithm in opportunistic network [J]. Computer Engineering, 2011, 37(16):86-89.(in Chinese)

[8] Li Y, Hui P, Jin D, et al. Evaluating the impact of social selfishness on the epidemic routing in delay tolerant networks[J]. IEEE Communications Letters, 2010, 14(11):1026-1028.

[9] Huang W, Zhang S, Zhou W. Spray and wait routing based on position prediction in opportunistic networks[C]∥Proc of 2011 3rd IEEE International Conference on Computer Research and Development (ICCRD), 2011:232-236.

[10] Gibran K. The PRoPHET:A new annotated edition[M]. London:Oneworld Publications, 2012.

[11] Ker?nen A, Ott J, K?rkk?inen T. The ONE simulator for DTN protocol evaluation[C]∥Proc of the 2nd International Conference on Simulation Tools and Techniques, 2009:55.

附中文參考文獻(xiàn)：

[1] 熊永平，孫利民，牛建偉,等. 機(jī)會網(wǎng)絡(luò)[J]. 軟件學(xué)報(bào), 2009, 20(1):124-137.

[3] 胡四泉，汪紅兵，王俊峰. 機(jī)會型網(wǎng)絡(luò)研究綜述[J]. 計(jì)算機(jī)科學(xué), 2009, 36(10):32-37.

[7] 孫踐知，劉乃瑞，張迎新,等. 機(jī)會網(wǎng)絡(luò)典型路由算法性能分析[J]. 計(jì)算機(jī)工程, 2011, 37(16):86-89.

LIUHui,born in 1989,MS candidate,his research interest includes opportunistic network.

陳志剛(1964),男,湖南益陽人，博士，教授，CCF會員(E200005226S)，研究方向?yàn)榫W(wǎng)絡(luò)與分布式計(jì)算。E-mail:czg@csu.edu.cn

CHENZhi-gang,born in 1964,PhD,professor,CCF member(E200005226S),his research interests include wireless networks, and distributed computing.

吳嘉(1983),男,貴州貴陽人，博士生，CCF會員(E200039369M)，研究方向?yàn)闄C(jī)會網(wǎng)絡(luò)和軟件工程。E-mail:jiawu5110@163.com

WUJia,born in 1983,PhD candidate,CCF member(E200039369M),his research interests include opportunistic network, and software engineering.

王丹(1989),女,河北保定人，碩士生，研究方向?yàn)闄C(jī)會網(wǎng)絡(luò)。E-mail:csuwangdan@163.com

WANGDan,born in 1989,MS candidate,her research interest includes opportunistic network.

曾劍鋒(1988),男，湖南邵陽人，碩士生，研究方向?yàn)闄C(jī)會網(wǎng)絡(luò)。E-mail:zjf19881202@163.com

ZENGJian-feng,born in 1988,MS candidate,his research interest includes opportunistic network.

AnefficientforwardingstrategybasedonXORoperationinopportunisticnetwork

LIU Hui1,2，CHEN Zhi-gang1,2，WU Jia1,2，WANG Dan1,2，ZENG Jian-feng1

(1.School of Software,Central South University,Changsha 410075;2. “Mobile Health” Ministry of Education-China Mobile Joint Laboratory,Changsha 410083,China)

Through studying the ways of forwarding information in opportunistic networks,the communication nodes in the neighbourbood can be traversed and the two nodes can be compared.Through the form of the intersection,the neighbor node with the largest XOR is chosen as the next hop to transfer the information so that a communication path with maximum effectiveness is formed. Based on this analysis process, an efficient forwarding strategy based on XOR operation in opportunistic networks (FSXO) is proposed.The proposal is compared with classical algorithms in opportunistic networks,and the simulation results show that the proposed FSXO strategy can reduce the presence of invalid copy data at high transmission rates,thus effectively reduce the routing overhead and resource consumption.

opportunistic network;XOR operation;communication path;forwarding strategy

1007-130X(2014)11-2094-06

2014-06-06;

：2014-08-20

國家自然科學(xué)基金資助項(xiàng)目(61073186，61379057，61309001，61379110, 61103202)；教育部博士點(diǎn)基金優(yōu)先發(fā)展領(lǐng)域課題資助項(xiàng)目(20120162130008)；國家973計(jì)劃資助項(xiàng)目(2014CB046305)；教育部博士點(diǎn)基金新教師類資助項(xiàng)目(20110162120046)

TP391.02

：A

10.3969/j.issn.1007-130X.2014.11.007

劉輝(1989),男,湖南邵陽人，碩士生，研究方向?yàn)闄C(jī)會網(wǎng)絡(luò)。E-mail:liuhui19890510@163.com

通信地址：410075 湖南省長沙市中南大學(xué)鐵道校區(qū)軟件學(xué)院

Address:School of Software,Railway Campus,Central South University,Changsha 410075,Hunan,P.R.China