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

任 冬，陳民華，劉順輝

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

0 引 言

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

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

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

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

1 網絡模型與問題描述

1.1 網絡拓撲構建

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

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

(1)

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

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

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

1.2 前提條件

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

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

1.3 問題描述

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

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

2 LOBS算法

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

2.1 ACK消息快速產生機制

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

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

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

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

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

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

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

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

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

2.1.3 跨層刪除緩存消息機制

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

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

圖1 ACK消息快速產生機制流程圖

2.2 控制消息合并機制

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

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

該機制的思想是讓ACK消息信息列表與SV信息列表進行融合傳輸，以此來減少控制消息數(shù)，從而減少控制開銷。機制提出的依據是通過分析ACK消息信息列表可知其存儲結構與SV信息列表相同，ACK消息信息列表存儲結構如圖2所示，SV列表包含源地址(SourceAddress)字段、目的地址(DestAddress)字段、消息標識(Identify)。如圖3所示為改進的相遇節(jié)點通信過程，ACK消息信息列表與SV信息列表進行合并傳輸，這樣節(jié)點在一次交互過程中節(jié)省了單獨發(fā)送ACK列表消息所需的頭部控制字段，從而減少了網絡控制開銷。圖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消息快速產生機制，以廣播的方式傳輸這些數(shù)據消息，同時更新自身的SVA列表。節(jié)點B收到這些數(shù)據消息時，更新自身的ACKB消息信息列表。

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

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

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

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

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

3.2 性能分析

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

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

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

(2)

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

(3)

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

(4)

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

(5)

因此，

nnew

(6)

證畢。

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

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

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

(7)

采用控制消息合并機制之后，網路整體控制開銷為

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

(8)

因此，

Enew

(9)

證畢。

4 仿真分析

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

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

4.1 消息到達成功率

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

η=R/S。

(10)

如圖5所示，隨著消息生存時間增大，消息到達成功率先增大后減小。消息到達成功率先增大的原因是由于節(jié)點的緩存空間足夠，增大消息的生存時間，可以減少網絡中因生存時間不足而被節(jié)點丟棄的消息個數(shù)；消息到達成功率后減小的原因是隨著消息生存時間的增加，網絡中的消息副本數(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消息快速產生機制可以更快地刪除網絡中已到達目的節(jié)點的消息副本，從而快速清理了節(jié)點緩存空間，減少了節(jié)點因緩存不足而刪除緩存消息的個數(shù)。

圖5 消息到達成功率

4.2 平均跳數(shù)

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

(11)

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

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

圖6 平均跳數(shù)

4.3 平均傳輸時延

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

(12)

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

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

圖7 平均傳輸時延

4.4 歸一化控制開銷

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

C=MC/(MC+MD) 。

(13)

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

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

圖8 歸一化控制開銷

4.5 網絡吞吐量

網絡吞吐量指單位時間內網絡中成功傳輸數(shù)據消息的比特數(shù)，其計算公式為

Throughput=P/(Tend-Tstart) 。

(14)

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

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

圖9 網絡吞吐量

5 結束語

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

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