任 冬，陳民華，劉順輝

(重慶郵電大學 a.通信與信息工程學院;b.移動通信技術(shù)重慶市重點實驗室，重慶 400065)

0 引 言

機會網(wǎng)絡(luò)[1-2]是一種源節(jié)點與目的節(jié)點之間沒有完整的傳輸路徑，利用節(jié)點移動帶來的相遇機會來實現(xiàn)源節(jié)點與目的節(jié)點通信的移動自組織網(wǎng)絡(luò)。機會社會網(wǎng)絡(luò)[3]是一種節(jié)點設(shè)備由人類持有的特殊網(wǎng)絡(luò)，這種通信方式可以擺脫固定基礎(chǔ)設(shè)施的限制，為物聯(lián)網(wǎng)(Internet of Things,IOT)[4]的研究提供理論基礎(chǔ)。

由于機會社會網(wǎng)絡(luò)鏈路不完整，與傳統(tǒng)的無線自組織網(wǎng)絡(luò)相比，機會社會網(wǎng)絡(luò)的成功率較低、時延較大。為了提高消息成功率和減少消息傳輸時延來使其更好地適用于現(xiàn)實應(yīng)用場景，目前國內(nèi)外有很多關(guān)于基于社區(qū)的機會社會網(wǎng)絡(luò)多副本消息傳輸機制的文獻[5-10]。

基于社區(qū)的消息機會傳輸(Community based Message Opportunity Transmission,CMOT)路由算法[11]根據(jù)節(jié)點歷史訪問信息來對節(jié)點進行社區(qū)劃分。該算法增加ACK機制雖然可以減少消息副本進行無效的轉(zhuǎn)發(fā)，節(jié)省了網(wǎng)絡(luò)資源，但是單獨發(fā)送ACK控制消息會出現(xiàn)網(wǎng)絡(luò)控制開銷增大的問題。基于重疊社區(qū)的消息機會轉(zhuǎn)發(fā)(Message Opportunistic Forwarding based on Overlapping Communities,MOFOC)路由算法[12]是一種基于重疊社區(qū)的多副本消息路由算法，在消息到達目的節(jié)點時，目的節(jié)點需要向全網(wǎng)泛洪一個ACK控制消息來刪除網(wǎng)絡(luò)中的該消息副本，但只讓目的節(jié)點洪泛ACK控制消息會導致因網(wǎng)絡(luò)中消息副本刪除不及時而使得網(wǎng)絡(luò)資源浪費的問題。

為解決上述CMOT算法和MOFOC算法中所存在的網(wǎng)絡(luò)控制開銷[13]增大和網(wǎng)絡(luò)資源浪費的問題，本文提出了一種基于廣播策略的機會社會網(wǎng)絡(luò)低開銷路由算法(Low Overhead Routing Algorithm for Opportunistic Social Networks based on Broadcast Strategy,LOBS)。

1 網(wǎng)絡(luò)模型與問題描述

1.1 網(wǎng)絡(luò)拓撲構(gòu)建

在現(xiàn)實社會網(wǎng)絡(luò)中，每個人不僅單一地屬于某一個社區(qū)，而且可以是多個社區(qū)的成員。例如，學生在上課時間，教學樓是他們的活動社區(qū)；在吃飯時間，食堂是他們的活動社區(qū)；在休息時間，宿舍樓是他們的活動社區(qū)。因此，網(wǎng)絡(luò)中的節(jié)點可以屬于多個社區(qū)。本文基于上述網(wǎng)絡(luò)特征，對機會社會網(wǎng)絡(luò)建立基于重疊社區(qū)的網(wǎng)絡(luò)模型并給出如下定義。

定義1 網(wǎng)絡(luò)模型：將節(jié)點數(shù)為N、社區(qū)數(shù)為m的網(wǎng)絡(luò)定義為

(1)

定義2 等待間隔時間：網(wǎng)絡(luò)中節(jié)點與其他節(jié)點通信結(jié)束時到該節(jié)點下一次通信開始所等待的時間。

定義3 活躍社區(qū)：節(jié)點間通信比較頻繁的社區(qū)，即在活躍社區(qū)中，節(jié)點間的等待間隔時間比較短。

定義4 活躍社區(qū)集：節(jié)點所屬社區(qū)中所有活躍社區(qū)的集合組成活躍社區(qū)集，若節(jié)點只屬于一個社區(qū)，則該社區(qū)為此節(jié)點的活躍社區(qū)集。

1.2 前提條件

假設(shè)1：網(wǎng)絡(luò)中每個節(jié)點都知道自己當前所處的社區(qū)。

假設(shè)2：網(wǎng)絡(luò)中不存在自私節(jié)點和惡意節(jié)點，消息在傳輸過程中只要滿足轉(zhuǎn)發(fā)條件，節(jié)點就對消息進行轉(zhuǎn)發(fā)。

1.3 問題描述

問題1：現(xiàn)有多副本消息傳輸機制(例如CMOT算法、MOFOC算法)中，當目的節(jié)點成功收到數(shù)據(jù)消息時，目的節(jié)點會產(chǎn)生一個ACK確認消息并通過泛洪的方式來刪除網(wǎng)絡(luò)中該數(shù)據(jù)消息的副本。但是，在目的節(jié)點成功接收數(shù)據(jù)消息時刻，只有目的節(jié)點一個節(jié)點產(chǎn)生ACK確認消息，這會導致網(wǎng)絡(luò)中數(shù)據(jù)消息副本因刪除不及時而產(chǎn)生不必要的轉(zhuǎn)發(fā)，浪費了網(wǎng)絡(luò)資源。

問題2：現(xiàn)有多副本消息傳輸機制中，當節(jié)點成功接收消息時，需要單獨泛洪一個ACK消息來消除網(wǎng)絡(luò)中的數(shù)據(jù)消息副本數(shù)，這會導致網(wǎng)絡(luò)的開銷增大。

2 LOBS算法

為解決上節(jié)所述問題，筆者提出了一種基于廣播策略的機會社會網(wǎng)絡(luò)低開銷路由算法——LOBS。該算法主要包含了ACK消息快速產(chǎn)生機制、控制消息合并機制兩種新機制，能有效減少網(wǎng)絡(luò)中數(shù)據(jù)消息副本不必要的轉(zhuǎn)發(fā)次數(shù)，以此來減少網(wǎng)絡(luò)資源的浪費，并且縮減節(jié)點交互過程中的控制消息，以此來減少網(wǎng)絡(luò)開銷。

2.1 ACK消息快速產(chǎn)生機制

ACK消息快速產(chǎn)生機制由以下三個子機制相互關(guān)聯(lián)來實現(xiàn)：廣播數(shù)據(jù)消息機制、跨層發(fā)送ACK消息機制和跨層刪除緩存消息機制。其核心思想是，在不增加額外控制開銷的前提下，不僅要保證消息到達成功率不受影響，同時還要加快ACK消息的產(chǎn)生，以此來快速刪除網(wǎng)絡(luò)中的消息副本，從而節(jié)省網(wǎng)絡(luò)資源。

2.1.1 廣播數(shù)據(jù)消息機制

攜帶消息節(jié)點與消息目的節(jié)點相遇時(最后一跳轉(zhuǎn)發(fā)數(shù)據(jù)消息)，節(jié)點數(shù)據(jù)鏈路層由原來的單播方式變?yōu)椴捎脧V播的方式傳輸數(shù)據(jù)幀。此時，不僅目的節(jié)點可以成功接收到該消息，攜帶消息節(jié)點的鄰居節(jié)點也可以接收到該消息。攜帶消息節(jié)點的鄰居節(jié)點數(shù)據(jù)鏈路層收到廣播數(shù)據(jù)幀時，對該數(shù)據(jù)幀進行解封，將解封之后的數(shù)據(jù)消息送到網(wǎng)絡(luò)層，并跨層通知網(wǎng)絡(luò)層該數(shù)據(jù)消息是通過廣播方式傳輸?shù)?。網(wǎng)絡(luò)層收到該數(shù)據(jù)消息時，判斷該消息的目的地址是否與自身地址相等，若是，則表明自身是消息目的節(jié)點，接收此數(shù)據(jù)消息；若不是，則表明這是一個已到達目的節(jié)點的數(shù)據(jù)消息，節(jié)點從自身緩存中刪除該數(shù)據(jù)消息副本，從而對緩存空間進行有效管理。同時鄰居節(jié)點按照數(shù)據(jù)結(jié)構(gòu)記錄與數(shù)據(jù)消息相對應(yīng)的ACK消息的信息(SourceAddress表示數(shù)據(jù)消息的源地址，DestAddress表示數(shù)據(jù)消息的目的地址，Identify表示數(shù)據(jù)消息的標識，TTL表示當前該數(shù)據(jù)消息所剩的生存時間)。當TTL=0時，表示該數(shù)據(jù)消息的生存時間到期，此時網(wǎng)絡(luò)中該數(shù)據(jù)消息的副本會自動被節(jié)點刪除，因此每個節(jié)點從ACK消息信息列表中刪除該消息的信息記錄；當TTL>0時，表示數(shù)據(jù)消息生存時間還沒有到期，全網(wǎng)可能還有該消息的副本，此時節(jié)點通過泛洪的方式發(fā)送ACK消息信息列表來刪除網(wǎng)絡(luò)中的消息副本。

通過采用廣播的方式進行最后一跳數(shù)據(jù)消息的傳輸來快速地產(chǎn)生ACK消息，其作用是為了更快地刪除網(wǎng)絡(luò)中的消息副本數(shù)，從而減少節(jié)點緩存空間的占用率以及減少網(wǎng)絡(luò)中的數(shù)據(jù)消息副本不必要的轉(zhuǎn)發(fā)次數(shù)。

由于無線網(wǎng)絡(luò)中數(shù)據(jù)鏈路層對于廣播消息不進行確認和重傳，即接收節(jié)點對于廣播消息不需要進行回復。廣播數(shù)據(jù)消息機制中數(shù)據(jù)消息最后一跳采用廣播方式傳輸，而由于數(shù)據(jù)鏈路層不對廣播消息進行ACK幀確認，因此攜帶消息節(jié)點無法保證目的節(jié)點是否成功接收該數(shù)據(jù)消息。為了解決這個問題，筆者提出了跨層發(fā)送ACK消息機制。

2.1.2 跨層發(fā)送ACK消息機制

目的節(jié)點數(shù)據(jù)鏈路層收到了該數(shù)據(jù)消息的廣播幀時，將該廣播幀解封后送到網(wǎng)絡(luò)層，若網(wǎng)絡(luò)層發(fā)現(xiàn)該數(shù)據(jù)消息的目的地址與自身地址相同，則表明自身為消息目的節(jié)點，此時網(wǎng)絡(luò)層跨層通知數(shù)據(jù)鏈路層向攜帶消息節(jié)點發(fā)送ACK幀。若攜帶消息節(jié)點收到ACK幀，則表示消息成功到達目的節(jié)點；若攜帶消息節(jié)點沒有收到ACK幀，則表明目的節(jié)點沒有成功接收消息，攜帶消息節(jié)點需要繼續(xù)重傳該數(shù)據(jù)消息。

由于單播數(shù)據(jù)幀的情況下，目的節(jié)點數(shù)據(jù)鏈路層需要對收到的數(shù)據(jù)幀回復ACK幀，因此跨層發(fā)送ACK消息機制中讓目的節(jié)點收到廣播數(shù)據(jù)幀后也回復ACK幀的方式并沒有比原來單播數(shù)據(jù)幀的方式增加節(jié)點額外控制開銷。

在廣播數(shù)據(jù)消息機制中提到數(shù)據(jù)消息可以被攜帶消息節(jié)點的鄰居節(jié)點接收到，但鄰居節(jié)點(除目的節(jié)點外的鄰居節(jié)點)并不是剛接收到該數(shù)據(jù)消息，節(jié)點網(wǎng)絡(luò)層就將緩存中的此數(shù)據(jù)消息刪除。原因在于數(shù)據(jù)消息廣播傳輸時，目的節(jié)點有可能沒有成功接收該數(shù)據(jù)消息，若沒有成功接收，則攜帶消息節(jié)點的鄰居節(jié)點不能刪除緩存中的該數(shù)據(jù)消息，以此來保證消息的投遞成功率；若成功接收，則直接刪除緩存中的該數(shù)據(jù)消息。因此，攜帶消息節(jié)點的鄰居節(jié)點何時在緩存中刪除該數(shù)據(jù)消息便成為一個需要解決的問題。為了解決這個問題，筆者提出了跨層刪除緩存消息機制。

2.1.3 跨層刪除緩存消息機制

攜帶消息節(jié)點的鄰居節(jié)點在接收到該數(shù)據(jù)消息之后，節(jié)點數(shù)據(jù)鏈路層繼續(xù)監(jiān)聽攜帶消息節(jié)點是否發(fā)送了重傳幀。若鄰居節(jié)點的數(shù)據(jù)鏈路層在規(guī)定的重傳時間內(nèi)收到的幀數(shù)(重傳幀和錯幀)小于3，則認為該數(shù)據(jù)消息發(fā)送成功，數(shù)據(jù)鏈路層跨層通知網(wǎng)絡(luò)層刪除緩存中該數(shù)據(jù)消息，同時在ACK消息信息列表中記錄相應(yīng)的數(shù)據(jù)消息信息；否則不處理緩存中的該數(shù)據(jù)消息。

ACK消息快速產(chǎn)生機制具體實現(xiàn)流程如圖1所示。該機制實現(xiàn)了在不增加額外控制開銷的前提下，不僅保證了消息到達成功率不受影響，同時還加快了ACK消息的產(chǎn)生，使得刪除網(wǎng)絡(luò)中的消息副本速度更快，減少了消息副本不必要的轉(zhuǎn)發(fā)次數(shù)，從而節(jié)省了網(wǎng)絡(luò)資源。

圖1 ACK消息快速產(chǎn)生機制流程圖

2.2 控制消息合并機制

現(xiàn)有基于社區(qū)的多副本消息傳輸機制中相遇節(jié)點的通信過程如圖2所示。當前節(jié)點與相遇節(jié)點在收到對方的Hello消息后，雙方會單獨發(fā)送一個ACK信息列表(含有多個數(shù)據(jù)消息的ACK信息)消息和一個SV信息列表消息給對方，此交互過程存在冗余。為了減少網(wǎng)絡(luò)控制開銷，筆者提出了控制消息合并機制。

圖2 相遇節(jié)點交互模型

該機制的思想是讓ACK消息信息列表與SV信息列表進行融合傳輸，以此來減少控制消息數(shù)，從而減少控制開銷。機制提出的依據(jù)是通過分析ACK消息信息列表可知其存儲結(jié)構(gòu)與SV信息列表相同，ACK消息信息列表存儲結(jié)構(gòu)如圖2所示，SV列表包含源地址(SourceAddress)字段、目的地址(DestAddress)字段、消息標識(Identify)。如圖3所示為改進的相遇節(jié)點通信過程，ACK消息信息列表與SV信息列表進行合并傳輸，這樣節(jié)點在一次交互過程中節(jié)省了單獨發(fā)送ACK列表消息所需的頭部控制字段，從而減少了網(wǎng)絡(luò)控制開銷。圖4所示為ACK列表與SV列表合并后的包格式信息。

圖3 改進的相遇節(jié)點交互過程

圖4 列表合并后的包格式信息

3 LOBS算法操作和性能分析

3.1 算法操作

LOBS算法的具體操作步驟如下：

Step1 節(jié)點A收到節(jié)點B的Hello消息時，則表示節(jié)點B與節(jié)點A相遇，此時節(jié)點B是節(jié)點A的鄰居節(jié)點，節(jié)點A記錄自身的等待間隔時間以及當前的社區(qū)號并更新自身所屬的活躍社區(qū)集合。

Step2 若節(jié)點A的緩存中有消息目的節(jié)點是節(jié)點B的消息，則執(zhí)行在不增加控制開銷的前提下ACK消息快速產(chǎn)生機制，以廣播的方式傳輸這些數(shù)據(jù)消息，同時更新自身的SVA列表。節(jié)點B收到這些數(shù)據(jù)消息時，更新自身的ACKB消息信息列表。

Step3 節(jié)點A采用控制消息合并機制向節(jié)點B發(fā)送SVA列表和ACKA消息信息列表。同時，節(jié)點A發(fā)送自身所屬的活躍社區(qū)集合信息。

Step4 節(jié)點B收到節(jié)點A的ACKA消息信息列表后，更新自身的SVB列表，同時更新自身的ACKB消息信息列表。接著，根據(jù)節(jié)點A的SVA列表摘要信息和所屬活躍社區(qū)集合信息，節(jié)點B向節(jié)點A發(fā)送自身SVB列表中沒有而SVA列表中含有的摘要信息所對應(yīng)的消息投遞概率或者間接集合活躍度信息。

Step5 節(jié)點A收到節(jié)點B的投遞概率列表信息和間接集合活躍度列表信息后，通過結(jié)合節(jié)點B所屬的活躍社區(qū)集合，節(jié)點A將滿足轉(zhuǎn)發(fā)條件的數(shù)據(jù)消息轉(zhuǎn)發(fā)給節(jié)點B。

Step6 節(jié)點B收到節(jié)點A轉(zhuǎn)發(fā)的數(shù)據(jù)消息后，對數(shù)據(jù)消息進行存儲、攜帶，同時更新自身的SVB列表。

以上是節(jié)點A收到節(jié)點B的Hello消息后，雙方節(jié)點所執(zhí)行的操作流程。同理，節(jié)點B收到節(jié)點A的Hello消息后，也執(zhí)行相同的操作，以此來完成雙方節(jié)點數(shù)據(jù)消息的轉(zhuǎn)發(fā)。

3.2 性能分析

新機制采用ACK消息快速產(chǎn)生機制來快速產(chǎn)生ACK消息，從而有效地減少網(wǎng)絡(luò)中的數(shù)據(jù)消息副本不必要的轉(zhuǎn)發(fā)次數(shù)，節(jié)省了網(wǎng)絡(luò)資源；采用控制消息合并機制來對控制消息進行合并，從而減少了消息交互過程中的控制開銷。下面對新機制進行理論分析。

引理1：與現(xiàn)有的多副本消息傳輸機制相比，LOBS協(xié)議刪除網(wǎng)絡(luò)中的消息副本速度更快。

證明：假設(shè)網(wǎng)絡(luò)中的節(jié)點數(shù)為N，每個節(jié)點的平均鄰居節(jié)點數(shù)為m(m>1)，那么其中一個節(jié)點洪泛一個ACK消息時，假設(shè)ACK消息轉(zhuǎn)發(fā)了norig次之后，全網(wǎng)絡(luò)的節(jié)點都可以接收到該ACK消息，此時,

(2)

因此，可以求出ACK消息的轉(zhuǎn)發(fā)次數(shù)

(3)

采用ACK消息快速產(chǎn)生機制之后，假設(shè)ACK消息轉(zhuǎn)發(fā)了nnew次之后，全網(wǎng)絡(luò)的節(jié)點都可以接收到該ACK消息，此時，

(4)

因此，ACK消息的轉(zhuǎn)發(fā)次數(shù)為

(5)

因此，

nnew

(6)

證畢。

引理2：與現(xiàn)有的多副本消息傳輸機制相比，LOBS協(xié)議的網(wǎng)絡(luò)控制開銷更低。

證明：假設(shè)網(wǎng)絡(luò)中的節(jié)點數(shù)為N，每個節(jié)點除去發(fā)送SV列表、ACK列表消息之外的其他控制消息所消耗的能量總和為K，節(jié)點發(fā)送控制消息每比特需要的能耗為δ，SV列表一共有a比特，ACK列表一共有b比特，發(fā)送控制消息頭部信息所需的能耗為β，因此網(wǎng)絡(luò)整體控制開銷為

Eorig=N(K+aδ+β+bδ+β)=N[K+(a+b)δ+2β] 。

(7)

采用控制消息合并機制之后，網(wǎng)路整體控制開銷為

Enew=N[K+(a+b)δ+β] 。

(8)

因此，

Enew

(9)

證畢。

4 仿真分析

本文采用OPNET14.5網(wǎng)絡(luò)仿真軟件對LOBS算法的消息到達成功率、平均跳數(shù)、平均傳輸時延、歸一化控制開銷和網(wǎng)絡(luò)吞吐量的網(wǎng)絡(luò)性能進行仿真驗證，并將仿真結(jié)果同CMOT算法和MOFOC算法的仿真結(jié)果進行對比分析。仿真參數(shù)設(shè)置見表1。

表1 仿真參數(shù)設(shè)置

4.1 消息到達成功率

消息到達成功率是指所有目的節(jié)點接收到的數(shù)據(jù)總量R與所有源節(jié)點產(chǎn)生的數(shù)據(jù)總數(shù)S的比值，計算公式為

η=R/S。

(10)

如圖5所示，隨著消息生存時間增大，消息到達成功率先增大后減小。消息到達成功率先增大的原因是由于節(jié)點的緩存空間足夠，增大消息的生存時間，可以減少網(wǎng)絡(luò)中因生存時間不足而被節(jié)點丟棄的消息個數(shù)；消息到達成功率后減小的原因是隨著消息生存時間的增加，網(wǎng)絡(luò)中的消息副本數(shù)增多，導致部分節(jié)點因緩存空間不足而刪除緩存中的消息，從而造成消息到達成功率減小。從圖中還可以看出，LOBS協(xié)議和MOFOC協(xié)議相較于CMOT協(xié)議的消息到達成功率更高，原因是LOBS協(xié)議和MOFOC協(xié)議是基于重疊社區(qū)劃分節(jié)點社區(qū)歸屬，相比于單社區(qū)劃分的CMOT協(xié)議，節(jié)點社區(qū)劃分更合理，因此消息到達成功率更高。在消息生存時間150～300 s時，LOBS協(xié)議和MOFOC協(xié)議消息到達率相近。原因是LOBS和MOFOC協(xié)議社區(qū)劃分機制都是基于重疊社區(qū)，在消息生存時間較小時，消息副本較少，節(jié)點緩存空間充足，所以兩協(xié)議消息到達率相近。在消息生存時間300～400 s時，LOBS協(xié)議比MOFOC協(xié)議的消息到達成功率稍高，原因是LOBS協(xié)議采用ACK消息快速產(chǎn)生機制可以更快地刪除網(wǎng)絡(luò)中已到達目的節(jié)點的消息副本，從而快速清理了節(jié)點緩存空間，減少了節(jié)點因緩存不足而刪除緩存消息的個數(shù)。

圖5 消息到達成功率

4.2 平均跳數(shù)

平均跳數(shù)指數(shù)據(jù)消息成功傳輸?shù)侥康墓?jié)點所需經(jīng)過的平均節(jié)點個數(shù)，其計算公式為

(11)

式中：D表示數(shù)據(jù)消息到達目的節(jié)點的個數(shù)，Hopi表示第i個數(shù)據(jù)消息到達目的節(jié)點所經(jīng)過的節(jié)點個數(shù)。

如圖6所示，LOBS協(xié)議與MOFOC協(xié)議的平均跳數(shù)比COMT協(xié)議多，其原因是COMT協(xié)議在社區(qū)內(nèi)傳輸消息時采用改進的PROPHET算法，只選擇目的節(jié)點的一跳節(jié)點作為轉(zhuǎn)發(fā)節(jié)點，因此減少了消息轉(zhuǎn)發(fā)跳數(shù)。LOBS協(xié)議與MOFOC協(xié)議的平均跳數(shù)相近，原因是LOBS協(xié)議的控制消息合并機制節(jié)省了消息頭部控制開銷，但是對消息的轉(zhuǎn)發(fā)跳數(shù)沒有影響；ACK消息快速產(chǎn)生機制快速地刪除了網(wǎng)絡(luò)中無用消息副本傳輸數(shù)量，但是對于消息到達目的節(jié)點的轉(zhuǎn)發(fā)跳數(shù)幾乎沒有影響。

圖6 平均跳數(shù)

4.3 平均傳輸時延

平均傳輸時延表示數(shù)據(jù)消息成功傳輸?shù)侥康墓?jié)點所需要的平均時間，其計算公式是

(12)

式中：D表示數(shù)據(jù)消息到達目的節(jié)點的個數(shù),Ti表示第i個消息到達目的節(jié)點的時延。

如圖7所示，隨著消息生存時間增大，消息平均傳輸時延先增大后減小。消息平均傳輸時延先增大的原因是節(jié)點在緩存空間足夠的情況下，消息生存時間越大，投遞率低的消息在緩存中生存的時間也就越久；后減小的原因是網(wǎng)絡(luò)中部分節(jié)點緩存空間不足，節(jié)點需要刪除緩存中投遞率低的消息來釋放緩存空間，從而導致平均傳輸時延減小。從圖中可以看出，LOBS協(xié)議和MOFOC協(xié)議相較于CMOT協(xié)議的平均傳輸時延較小，原因是：LOBS協(xié)議和MOFOC協(xié)議是基于重疊社區(qū)劃分節(jié)點社區(qū)歸屬，節(jié)點社區(qū)劃分更合理；CMOT協(xié)議在社區(qū)內(nèi)采用改進的PROPHET算法來限制消息副本數(shù)量，這會導致消息時延增加。在消息生存時間300 s之前LOBS和MOFOC平均時延相近的原因是由于節(jié)點的緩存空間足夠，消息到達環(huán)境相同，故兩種算法在生存時間較短時平均傳輸時延基本一致。在300 s后LOBS協(xié)議比MOFOC協(xié)議平均傳輸時延大的原因是采用ACK消息快速產(chǎn)生機制快速地清理了節(jié)點緩存中已到達目的節(jié)點的消息副本，減少了節(jié)點因緩存不足而刪除緩存中投遞率低的消息數(shù)，從而投遞率較低的消息得到轉(zhuǎn)發(fā)，而這些投遞率較低的消息傳輸時延也比較大，因此增加了平均傳輸時延。

圖7 平均傳輸時延

4.4 歸一化控制開銷

歸一化控制開銷指網(wǎng)絡(luò)中節(jié)點發(fā)送的控制消息總比特數(shù)與控制消息和到達目的節(jié)點數(shù)據(jù)消息總比特數(shù)的比值，其值越大表示網(wǎng)絡(luò)開銷也越大，計算公式是

C=MC/(MC+MD) 。

(13)

式中：MC表示網(wǎng)絡(luò)中控制消息總比特數(shù)，MD表示網(wǎng)絡(luò)中到達目的節(jié)點數(shù)據(jù)消息總比特數(shù)。

如圖8所示，隨著消息生存時間增大，歸一化控制開銷先減少后增大。歸一化控制開銷先減少的原因是消息生存時間增大會提高消息到達成功率，從而增加了網(wǎng)絡(luò)中到達目的節(jié)點的數(shù)據(jù)消息總數(shù)，而節(jié)點的控制消息總數(shù)只與節(jié)點間的相遇次數(shù)有關(guān)，與消息生存時間無關(guān)，因此在消息生存時間增大的過程中，歸一化控制開銷在不斷減?。缓笤龃蟮脑蚴窍⑸鏁r間在300～400 s的時候，網(wǎng)絡(luò)中部分節(jié)點緩存空間不足，導致消息到達成功率降低，從而使得歸一化控制開銷增大。從圖中可以看出，與CMOT協(xié)議和MOFOC協(xié)議相比，LOBS協(xié)議的歸一化控制開銷更低，主要原因是：在不增加控制開銷的前提下ACK消息快速產(chǎn)生機制可以快速地刪除網(wǎng)絡(luò)中無用消息副本傳輸數(shù)量，減少了無用消息副本的轉(zhuǎn)發(fā)次數(shù)，從而減少了控制消息總比特數(shù)，因此降低了網(wǎng)絡(luò)控制開銷；控制消息合并機制減少了控制消息總數(shù)，節(jié)省了消息頭部控制開銷，從而降低了網(wǎng)絡(luò)控制開銷。

圖8 歸一化控制開銷

4.5 網(wǎng)絡(luò)吞吐量

網(wǎng)絡(luò)吞吐量指單位時間內(nèi)網(wǎng)絡(luò)中成功傳輸數(shù)據(jù)消息的比特數(shù)，其計算公式為

Throughput=P/(Tend-Tstart) 。

(14)

式中：P表示數(shù)據(jù)消息到達目的節(jié)點的總比特數(shù)，Tstart表示網(wǎng)絡(luò)仿真開始時間，Tend表示網(wǎng)絡(luò)仿真結(jié)束時間。

如圖9所示，隨著消息生存時間增大，網(wǎng)絡(luò)吞吐量先增大后減小。吞吐量先增大的原因是消息生存時間增大，成功傳輸?shù)侥康墓?jié)點的數(shù)據(jù)消息就增多，從而使得網(wǎng)絡(luò)吞吐量增大；后減小的原因是網(wǎng)絡(luò)中部分節(jié)點緩存空間不足，導致節(jié)點因釋放緩存空間而刪除緩存消息，從而成功傳輸?shù)侥康墓?jié)點的數(shù)據(jù)消息數(shù)就會減少。從圖中可以看出，LOBS協(xié)議的網(wǎng)絡(luò)吞吐量高于CMOT協(xié)議和MOFOC協(xié)議，主要原因是LOBS協(xié)議采用在不增加控制開銷的前提下ACK消息快速產(chǎn)生機制可以更加快速地刪除網(wǎng)絡(luò)中已到達目的節(jié)點的消息副本，從而快速地清理了節(jié)點緩存空間，減少了節(jié)點因緩存不足而刪除緩存消息的個數(shù)，從而成功傳輸?shù)侥康墓?jié)點的消息數(shù)就增多。

圖9 網(wǎng)絡(luò)吞吐量

5 結(jié)束語

本文針對現(xiàn)有機會社會網(wǎng)絡(luò)多副本消息傳輸機制中網(wǎng)絡(luò)控制開銷較大和網(wǎng)絡(luò)資源浪費的問題，提出了一種基于廣播策略的機會社會網(wǎng)絡(luò)低開銷路由算法。該算法由ACK消息快速產(chǎn)生機制和控制消息合并機制兩種新機制組成。通過采用ACK消息快速產(chǎn)生機制來快速刪除網(wǎng)絡(luò)中已到達消息目的節(jié)點的消息副本，減少此類消息不必要的轉(zhuǎn)發(fā)次數(shù)，使網(wǎng)絡(luò)中投遞率較低的消息也得到有效轉(zhuǎn)發(fā)，從而節(jié)省了網(wǎng)絡(luò)資源；采用控制消息合并機制縮減了消息交互過程中的控制開銷，網(wǎng)絡(luò)性能得到有效提升。

由于機會社會網(wǎng)絡(luò)中消息到達成功率仍較低，因此，今后的工作是對機會社會網(wǎng)絡(luò)的路由轉(zhuǎn)發(fā)策略進行研究。