移動群智感知中基于節(jié)點競爭的數(shù)據(jù)轉(zhuǎn)發(fā)算法

王巧莉，張振宇,，吳曉紅

（1.新疆大學(xué)信息科學(xué)與工程學(xué)院，烏魯木齊830046；2.新疆大學(xué)軟件學(xué)院，烏魯木齊830008）

群智感知；剩余能量比；節(jié)點活躍度；關(guān)系強度；數(shù)據(jù)轉(zhuǎn)發(fā)

0 引言

隨著大規(guī)模感知和數(shù)據(jù)傳輸技術(shù)的進步，我們已經(jīng)進入了物聯(lián)網(wǎng)時代。越來越多的用戶設(shè)備嵌入了各種各樣的傳感器，諸如重力傳感器、溫度計、加速度傳感器等，這些傳感器可以對人類活動及周圍環(huán)境進行全方位的感知。群智感知在云端聚合每個用戶設(shè)備感知到的信息（如環(huán)境上下文噪聲等級、交通狀況等）進行進一步的感知和群體智能的挖掘[1]。

群智感知是以人為中心的網(wǎng)絡(luò)，持有感知設(shè)備的用戶具有移動性，這使群智感知網(wǎng)絡(luò)和傳統(tǒng)的傳感器網(wǎng)絡(luò)有很大的不同，表現(xiàn)為部署更加靈活，成本更低廉等；另外人的移動性也提供了更多的機會進行感知覆蓋和數(shù)據(jù)傳輸。在傳輸感知數(shù)據(jù)時，有時并不具備連接蜂窩網(wǎng)絡(luò)或者互聯(lián)網(wǎng)的方式進行[2]。感知應(yīng)用往往會產(chǎn)生大量的數(shù)據(jù)，會使用戶產(chǎn)生大量的流量費用，消耗過多的電量，導(dǎo)致成本過高，并且給蜂窩網(wǎng)絡(luò)帶來了很大的壓力。當移動設(shè)備密度大，接觸頻繁，為傳輸帶來更多的機會時，可以使用“存儲-攜帶-轉(zhuǎn)發(fā)”的工作模式進行感知數(shù)據(jù)的傳輸[3]。目前的移動設(shè)備利用短距離通信技術(shù)進行數(shù)據(jù)的傳輸，直到遇到有充足的電量流量并能夠把數(shù)據(jù)上傳至數(shù)據(jù)中心的終端設(shè)備。

1 相關(guān)工作

在現(xiàn)有的機會傳輸方式中，最具代表性的是Epi?demic[4]算法，算法采用的是洪泛策略，每個節(jié)點都把接收到的消息轉(zhuǎn)發(fā)給自己的鄰居節(jié)點，直至傳至目的節(jié)點。該方法雖然能得到較高的傳輸成功率，但是會耗費大量的網(wǎng)絡(luò)資源。Prophet[5]采用的是概率策略，出于對現(xiàn)實中人的移動行為具有重復(fù)性的考慮，根據(jù)歷史相遇信息計算節(jié)點間的傳輸概率。Spray and Wait[6]也是基于泛洪策略的算法，但在節(jié)點相遇時對產(chǎn)生的副本個數(shù)進行不同程度的限制，在Spray階段，向網(wǎng)絡(luò)中注入限定數(shù)量的副本，在Wait階段，持有這些副本的節(jié)點直至遇到目的節(jié)點后才進行數(shù)據(jù)的交付。

以上路由算法都是從持有消息的節(jié)點出發(fā)，力求找到最優(yōu)的中繼節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)直至到達目的節(jié)點，但是并未充分調(diào)動所有節(jié)點參與數(shù)據(jù)轉(zhuǎn)發(fā)的積極性。本文針對移動群智感知網(wǎng)絡(luò)場景，提出一種基于節(jié)點競爭的轉(zhuǎn)發(fā)算法，該算法通過設(shè)計競爭服務(wù)策略，通過對節(jié)點的剩余能量、節(jié)點活躍度、節(jié)點關(guān)系強度、歷史轉(zhuǎn)發(fā)次數(shù)等影響因子的綜合考量，得到最優(yōu)的轉(zhuǎn)發(fā)節(jié)點，同時給予競爭成功的節(jié)點相應(yīng)的報酬，從而充分調(diào)動通信范圍內(nèi)節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā)的積極性，使更多的節(jié)點能夠參與到數(shù)據(jù)轉(zhuǎn)發(fā)的過程中，加速數(shù)據(jù)的轉(zhuǎn)發(fā)。

2 基于節(jié)點競爭的轉(zhuǎn)發(fā)算法

2.1 網(wǎng)絡(luò)模型

在移動群智感知網(wǎng)絡(luò)中，持有感知傳輸設(shè)備的人組成了其中的移動節(jié)點，在城市中移動節(jié)點的密度較大，節(jié)點之間會產(chǎn)生更多的相遇機會，可以充分利用這些節(jié)點之間的相遇機會進行數(shù)據(jù)的轉(zhuǎn)發(fā)。節(jié)點之間采用“存儲-攜帶-轉(zhuǎn)發(fā)”的工作模式，利用設(shè)備具有的短距離無線通信技術(shù)進行數(shù)據(jù)的交互。持有待轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點設(shè)定好競爭條件，在通信范圍內(nèi)的節(jié)點感知到此信息后參與到競爭轉(zhuǎn)發(fā)數(shù)據(jù)的過程中，循環(huán)此過程直至到達目標節(jié)點。

圖1 節(jié)點競爭轉(zhuǎn)發(fā)模型

2.2 節(jié)點競爭力評價指標

（1）剩余能量比[7]：當我們對中繼節(jié)點進行選擇時，應(yīng)該首先考慮該節(jié)點的能量情況，通過節(jié)點剩余能量比來對節(jié)點的狀態(tài)進行判定，節(jié)點N在任意時刻t的剩余能量比表示為En（t），Emax為節(jié)點能夠達到的最大能量，Ecur為節(jié)點當前的剩余能量，其公式如（1）所示：

（2）節(jié)點活躍度[8]：首先本文將有限時間序列T劃分為以τ為時間間隔的p個時間間隔，那么第m個時間間隔為τm（m＜p），若將在時間間隔τ內(nèi)與節(jié)點i相遇的節(jié)點設(shè)為集合Si={v1,v2,v3…vn}，則第m-1個時間間隔內(nèi)節(jié)點i的相遇節(jié)點集合為Si(τm-1)，相應(yīng)的在第m個時間間隔內(nèi)節(jié)點i與其他節(jié)點相遇的集合為Si(τm)，因此我們將節(jié)點i在時間間隔為τm中的活躍度定義如下，其公式如（2）所示：

（3）節(jié)點關(guān)系強度：可以根據(jù)節(jié)點間的歷史相遇次數(shù)來對節(jié)點間的社會關(guān)系進行衡量，在時間間隔τm內(nèi)，節(jié)點 Ni與節(jié)點 Nj之間的關(guān)系強度 F（i，j（）τm）可以根據(jù)公式（3）進行計算：

其中，E（i，j）（τm）表示節(jié)點 i與節(jié)點 j在時間間隔τm中的相遇次數(shù)，N（iτm）則表示在相同時間間隔內(nèi)，節(jié)點i與所有鄰居節(jié)點的相遇總次數(shù)。

（4）歷史轉(zhuǎn)發(fā)次數(shù)：節(jié)點參與消息成功轉(zhuǎn)發(fā)過程的次數(shù)一定程度上體現(xiàn)了節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)積極性和有效性，將節(jié)點i最近時間范圍內(nèi)的成功轉(zhuǎn)發(fā)次數(shù)設(shè)為Ci，此后根據(jù)節(jié)點的轉(zhuǎn)發(fā)情況對該值進行調(diào)整。

2.3 CBOF算法設(shè)計

網(wǎng)絡(luò)中的節(jié)點參與數(shù)據(jù)轉(zhuǎn)發(fā)的過程，或多或少都會耗費自己的資源來進行消息的轉(zhuǎn)發(fā)，從社會價值的角度分析，參與的節(jié)點都期望能夠獲得相應(yīng)的利益，而不是無償?shù)淖栽皋D(zhuǎn)發(fā)，考慮到這樣的情形，本文的研究中基于參與轉(zhuǎn)發(fā)的節(jié)點一定的資金收益，通過節(jié)點間競爭轉(zhuǎn)發(fā)獲得收益來有效調(diào)動節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)的積極性。因此，將競爭轉(zhuǎn)發(fā)信息CFM（Competition Forward?ing Messages）定義為如公式（4）所示的四元組：

其中的Dnode-ID轉(zhuǎn)發(fā)消息的目的節(jié)點，為其他節(jié)點發(fā)布當前的競爭轉(zhuǎn)發(fā)信息，F(xiàn)orwarding Messages為當前待轉(zhuǎn)發(fā)的消息，Time Strap為競爭時間窗，發(fā)布競爭消息后在該時間段內(nèi)接收競爭節(jié)點的信息，Reward為消息成功轉(zhuǎn)發(fā)至目的節(jié)點后，參與轉(zhuǎn)發(fā)過程的節(jié)點所獲得的相應(yīng)報酬。

首先假設(shè)此當前節(jié)點i需要將數(shù)據(jù)轉(zhuǎn)發(fā)至目的節(jié)點D。當節(jié)點i與j相遇時，需要對節(jié)點j的消息轉(zhuǎn)發(fā)能力 FA（Forwarding Ability）進行評價，如公式（5）所示計算：

節(jié)點j的整體效用值計算需要綜合考慮當前節(jié)點剩余能量比和消息轉(zhuǎn)發(fā)能力，計算過程如公式（6）所示：

基于節(jié)點競爭轉(zhuǎn)發(fā)的算法基本步驟如下：

假設(shè)目前有節(jié)點i需要轉(zhuǎn)發(fā)消息至目的節(jié)點D，那么節(jié)點i首先要向網(wǎng)絡(luò)中發(fā)布競爭轉(zhuǎn)發(fā)信息CFM（Competition Forwarding Messages），等待其他節(jié)點對該信息進行反饋，返回其競爭參與意愿，這里假設(shè)若目的節(jié)點感知到該信息，則不需要進行任何計算，直接返回目的節(jié)點確認消息即可，但其他參與競爭轉(zhuǎn)發(fā)消息過程的節(jié)點則應(yīng)根據(jù)公式（6）計算自身整體的效用值，并返回給競爭信息發(fā)布節(jié)點。

（1）若感知到該信息的節(jié)點中包含目的節(jié)點，則目的節(jié)點直接返回確認連接進行數(shù)據(jù)的交付，不需要對自身的效用值進行計算，交付成功后當前節(jié)點刪除消息；

（2）若感知到該信息的節(jié)點中不包含目的節(jié)點，則應(yīng)根據(jù)競爭轉(zhuǎn)發(fā)消息的節(jié)點反饋的效用值和歷史轉(zhuǎn)發(fā)次數(shù)選擇出最優(yōu)的競爭節(jié)點，進行數(shù)據(jù)的交付。當效用值最高的節(jié)點與其中一個節(jié)點相差的值小于給定的閾值ε時，則比對效用值最大的節(jié)點與該節(jié)點效用值之間的所有節(jié)點的歷史轉(zhuǎn)發(fā)次數(shù)，選出歷史轉(zhuǎn)發(fā)次數(shù)最高的節(jié)點，則該節(jié)點競爭成功，繼續(xù)消息的轉(zhuǎn)發(fā)過程，直至遇到目的節(jié)點。

3 實驗仿真

3.1 仿真參數(shù)與環(huán)境設(shè)置

本文通過ONE軟件[9]對CBOF算法進行仿真，仿真實驗中將節(jié)點的移動區(qū)域設(shè)置為5500m×4500m內(nèi)，模擬校園中行人真實行走場景，在該場景內(nèi)的每個行人的移動速度控制在0.5m/s-1.5m/s之間，具體參數(shù)設(shè)置如表1所示。

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

3.2 仿真結(jié)果與性能分析

算法的仿真結(jié)果評價指標為交付率、傳輸延遲、路由開銷[10]。

（1）節(jié)點數(shù)量相同

圖2 交付率隨節(jié)點數(shù)量變化圖

從圖2可以看出，當節(jié)點數(shù)量比較多的情況下，CBOF算法展現(xiàn)出了更優(yōu)的性能，這是由于隨著節(jié)點數(shù)量增大，使節(jié)點之間相遇的次數(shù)大大增加，使更多的節(jié)點參與競爭轉(zhuǎn)發(fā)的過程，從而選出最優(yōu)的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，并增大了與目的節(jié)點相遇的概率，獲得較高的交付率。Spray and Wait算法和Prophets算法則相對穩(wěn)定，并沒有隨節(jié)點數(shù)量變化發(fā)生明顯的波動。而Epidemic算法由于節(jié)點的增多導(dǎo)致副本數(shù)量增多，而在節(jié)點緩存一定的情況下，消息可能會出現(xiàn)溢出或者丟棄等現(xiàn)象導(dǎo)致交付率反而出現(xiàn)下降的趨勢。

圖3 傳輸延遲隨節(jié)點數(shù)量變化圖

如圖3所示，隨著節(jié)點數(shù)量的增多，四種算法的傳輸延遲均呈現(xiàn)下降趨勢，CBOF在節(jié)點數(shù)量增加到一定數(shù)量時延遲減小的程度較明顯，而Epidemic算法由于節(jié)點自身的緩存有限，并不能達到最優(yōu)的延遲性能，Prophet算法需要進行傳輸概率的計算，因此延遲高于其他算法。

圖4 路由開銷隨節(jié)點數(shù)量變化圖

從圖4可得節(jié)點數(shù)量的增多對Epidemic算法的路由開銷影響最大，因為算法中產(chǎn)生的副本數(shù)量最多，典型的以空間換時間的方法來提升性能，但節(jié)點的緩存往往很有限，有時適得其反。Prophet算法的路由開銷也有比較明顯的上升趨勢，而CBOF算法和Spray and Wait算法展現(xiàn)較為穩(wěn)定的性能，延遲均較低。

（2）緩存空間相同

圖5 交付率隨緩存大小變化圖

從圖5所呈現(xiàn)的結(jié)果來看，節(jié)點緩存的增加有利于提高消息的交付率，四種算法的交付率均出現(xiàn)明顯增加的情況，CBOF算法考慮了節(jié)點的剩余能量情況，提高節(jié)點參與轉(zhuǎn)發(fā)的積極性，充分利用緩存，因此得到了較好的性能，而Epidemic算法的交付率隨緩存的增加雖有上升的趨勢，但仍然無法與副本增長的速度所匹配。

如圖6所示，消息的傳輸延遲隨緩存增大而出現(xiàn)增加的趨勢，但是CBOF算法考慮節(jié)點能量情況以及節(jié)點活躍度等因素，充分利用了節(jié)點的緩存，并未出現(xiàn)較大的增加現(xiàn)象，而Epidemic算法因為洪泛策略產(chǎn)生的負面影響，傳輸延遲仍然較大。

圖6 傳輸延遲隨緩存大小變化圖

圖7 路由開銷隨緩存大小變化圖

根據(jù)圖7可以觀察到隨著節(jié)點緩存的增大，各算法的路由開銷均出現(xiàn)明顯下降趨勢，但Epidemic算法因此為自身特性仍然具有最大的路由開銷，CBOF算法則因為考慮了節(jié)點與新節(jié)點接觸的可能性，選擇社交關(guān)系較強的節(jié)點進行消息的轉(zhuǎn)發(fā)，使路由開銷較小。

（3）運行時間相同

圖8 交付率隨運行時間變化圖

圖8說明了隨運行時間的增長，交付率呈現(xiàn)出下降的趨勢，這是節(jié)點的緩存隨時間的增長而減小，使部分消息得不到有效轉(zhuǎn)發(fā)，造成消息整體的交付率下降，而CBOF算法在運行一段時間后仍然能保持較高的交付率，是因為均衡了網(wǎng)絡(luò)的能量利用及更多節(jié)點參與轉(zhuǎn)發(fā)對緩存狀況的緩解。

如圖9所示，CBOF所選擇的中繼節(jié)點能夠影響更多的新節(jié)點，從而增大與目的節(jié)點的傳輸概率，因而具有較低的傳輸延遲，在運行的初期，四種算法均出現(xiàn)了傳輸延遲快速下降的情況，但在運行的后期逐漸趨于穩(wěn)定。

圖10說明了隨著運行時間的增長，CBOF算法的路由開銷較小且趨于穩(wěn)定，Epidemic因為副本數(shù)量的劇增保持著最大的路由開銷，Prophet算法通過尋優(yōu)轉(zhuǎn)發(fā)節(jié)點一定程度降低了路由開銷，Spray and Wait算法只是在第一階段產(chǎn)生一定數(shù)量的副本，所以路由開銷并不大。

圖9 傳輸延遲隨運行時間變化圖

4 結(jié)語

本文針對群智感知中的數(shù)據(jù)轉(zhuǎn)發(fā)問題，提出一種基于節(jié)點競爭的轉(zhuǎn)發(fā)算法。通過對參與數(shù)據(jù)轉(zhuǎn)發(fā)的節(jié)點提供收益補償，調(diào)動節(jié)點參與競爭轉(zhuǎn)發(fā)的積極性，達到促進數(shù)據(jù)轉(zhuǎn)發(fā)的目的。根據(jù)節(jié)點的剩余能量、節(jié)點活躍度、節(jié)點關(guān)系強度、歷史轉(zhuǎn)發(fā)次數(shù)等屬性對參與競爭節(jié)點進行評價，將轉(zhuǎn)發(fā)能力強的節(jié)點作為中繼節(jié)點進行下一步的轉(zhuǎn)發(fā)。仿真結(jié)果表明，與Epidemic、Prophet及SW等算法相比，在保證較低網(wǎng)絡(luò)開銷的基礎(chǔ)上，能夠充分利用節(jié)點的轉(zhuǎn)發(fā)能力，從而提高數(shù)據(jù)交付率和減少延遲。

圖10 路由開銷隨運行時間變化圖