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

任 冬，陳民華，劉順輝

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

0 引 言

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

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

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

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

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

1.1 網(wǎng)絡(luò)拓?fù)錁?gòu)建

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

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

(1)

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

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

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

1.2 前提條件

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

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

1.3 問(wèn)題描述

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

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

2 LOBS算法

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

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

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

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

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

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

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

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

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

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

在廣播數(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ù)消息廣播傳輸時(shí)，目的節(jié)點(diǎn)有可能沒(méi)有成功接收該數(shù)據(jù)消息，若沒(méi)有成功接收，則攜帶消息節(jié)點(diǎn)的鄰居節(jié)點(diǎn)不能刪除緩存中的該數(shù)據(jù)消息，以此來(lái)保證消息的投遞成功率；若成功接收，則直接刪除緩存中的該數(shù)據(jù)消息。因此，攜帶消息節(jié)點(diǎn)的鄰居節(jié)點(diǎn)何時(shí)在緩存中刪除該數(shù)據(jù)消息便成為一個(gè)需要解決的問(wèn)題。為了解決這個(gè)問(wèn)題，筆者提出了跨層刪除緩存消息機(jī)制。

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

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

ACK消息快速產(chǎn)生機(jī)制具體實(shí)現(xiàn)流程如圖1所示。該機(jī)制實(shí)現(xiàn)了在不增加額外控制開(kāi)銷的前提下，不僅保證了消息到達(dá)成功率不受影響，同時(shí)還加快了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)的通信過(guò)程如圖2所示。當(dāng)前節(jié)點(diǎn)與相遇節(jié)點(diǎn)在收到對(duì)方的Hello消息后，雙方會(huì)單獨(dú)發(fā)送一個(gè)ACK信息列表(含有多個(gè)數(shù)據(jù)消息的ACK信息)消息和一個(gè)SV信息列表消息給對(duì)方，此交互過(guò)程存在冗余。為了減少網(wǎng)絡(luò)控制開(kāi)銷，筆者提出了控制消息合并機(jī)制。

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

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

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

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

3 LOBS算法操作和性能分析

3.1 算法操作

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

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

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

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

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

Step5 節(jié)點(diǎn)A收到節(jié)點(diǎn)B的投遞概率列表信息和間接集合活躍度列表信息后，通過(guò)結(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ù)消息后，對(duì)數(shù)據(jù)消息進(jìn)行存儲(chǔ)、攜帶，同時(shí)更新自身的SVB列表。

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

3.2 性能分析

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

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

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

(2)

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

(3)

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

(4)

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

(5)

因此，

nnew

(6)

證畢。

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

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

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

(7)

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

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

(8)

因此，

Enew

(9)

證畢。

4 仿真分析

本文采用OPNET14.5網(wǎng)絡(luò)仿真軟件對(duì)LOBS算法的消息到達(dá)成功率、平均跳數(shù)、平均傳輸時(shí)延、歸一化控制開(kāi)銷和網(wǎng)絡(luò)吞吐量的網(wǎng)絡(luò)性能進(jìn)行仿真驗(yàn)證，并將仿真結(jié)果同CMOT算法和MOFOC算法的仿真結(jié)果進(jìn)行對(duì)比分析。仿真參數(shù)設(shè)置見(jiàn)表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所示，隨著消息生存時(shí)間增大，消息到達(dá)成功率先增大后減小。消息到達(dá)成功率先增大的原因是由于節(jié)點(diǎn)的緩存空間足夠，增大消息的生存時(shí)間，可以減少網(wǎng)絡(luò)中因生存時(shí)間不足而被節(jié)點(diǎn)丟棄的消息個(gè)數(shù)；消息到達(dá)成功率后減小的原因是隨著消息生存時(shí)間的增加，網(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á)成功率更高。在消息生存時(shí)間150～300 s時(shí)，LOBS協(xié)議和MOFOC協(xié)議消息到達(dá)率相近。原因是LOBS和MOFOC協(xié)議社區(qū)劃分機(jī)制都是基于重疊社區(qū)，在消息生存時(shí)間較小時(shí)，消息副本較少，節(jié)點(diǎn)緩存空間充足，所以兩協(xié)議消息到達(dá)率相近。在消息生存時(shí)間300～400 s時(shí)，LOBS協(xié)議比MOFOC協(xié)議的消息到達(dá)成功率稍高，原因是LOBS協(xié)議采用ACK消息快速產(chǎn)生機(jī)制可以更快地刪除網(wǎng)絡(luò)中已到達(dá)目的節(jié)點(diǎn)的消息副本，從而快速清理了節(jié)點(diǎn)緩存空間，減少了節(jié)點(diǎn)因緩存不足而刪除緩存消息的個(gè)數(shù)。

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

4.2 平均跳數(shù)

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

(11)

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

如圖6所示，LOBS協(xié)議與MOFOC協(xié)議的平均跳數(shù)比COMT協(xié)議多，其原因是COMT協(xié)議在社區(qū)內(nèi)傳輸消息時(shí)采用改進(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é)省了消息頭部控制開(kāi)銷，但是對(duì)消息的轉(zhuǎn)發(fā)跳數(shù)沒(méi)有影響；ACK消息快速產(chǎn)生機(jī)制快速地刪除了網(wǎng)絡(luò)中無(wú)用消息副本傳輸數(shù)量，但是對(duì)于消息到達(dá)目的節(jié)點(diǎn)的轉(zhuǎn)發(fā)跳數(shù)幾乎沒(méi)有影響。

圖6 平均跳數(shù)

4.3 平均傳輸時(shí)延

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

(12)

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

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

圖7 平均傳輸時(shí)延

4.4 歸一化控制開(kāi)銷

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

圖8 歸一化控制開(kāi)銷

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

網(wǎng)絡(luò)吞吐量指單位時(shí)間內(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ò)仿真開(kāi)始時(shí)間，Tend表示網(wǎng)絡(luò)仿真結(jié)束時(shí)間。

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

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

5 結(jié)束語(yǔ)

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

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