一種控制消息廣播與合并策略的低開銷路由算法*

任 冬，陳民華，劉順輝

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

0 引 言

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

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

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

為解決上述CMOT算法和MOFOC算法中所存在的網(wǎng)絡(luò)控制開銷[13]增大和網(wǎng)絡(luò)資源浪費(fèi)的問題，本文提出了一種基于廣播策略的機(jī)會社會網(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ò)拓?fù)錁?gòu)建

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

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

(1)

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

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

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

1.2 前提條件

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

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

1.3 問題描述

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

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

2 LOBS算法

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

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

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

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

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

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

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

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

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

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

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

2.1.3 跨層刪除緩存消息機(jī)制

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

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

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

2.2 控制消息合并機(jī)制

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

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

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

圖3 改進(jìn)的相遇節(jié)點(diǎn)交互過程

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

3 LOBS算法操作和性能分析

3.1 算法操作

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

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

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

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

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

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

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

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

3.2 性能分析

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

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

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

(2)

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

(3)

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

(4)

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

(5)

因此，

nnew

(6)

證畢。

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

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

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

(7)

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

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

(8)

因此，

Enew

(9)

證畢。

4 仿真分析

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

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

4.1 消息到達(dá)成功率

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

η=R/S。

(10)

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

圖5 消息到達(dá)成功率

4.2 平均跳數(shù)

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

(11)

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

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

圖6 平均跳數(shù)

4.3 平均傳輸時延

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

(12)

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

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

圖7 平均傳輸時延

4.4 歸一化控制開銷

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

C=MC/(MC+MD) 。

(13)

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

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

圖8 歸一化控制開銷

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

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

Throughput=P/(Tend-Tstart) 。

(14)

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

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

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

5 結(jié)束語

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

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