移動群智感知中基于節點競爭的數據轉發算法

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

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

群智感知；剩余能量比；節點活躍度；關系強度；數據轉發

0 引言

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

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

1 相關工作

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

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

2 基于節點競爭的轉發算法

2.1 網絡模型

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

圖1 節點競爭轉發模型

2.2 節點競爭力評價指標

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

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

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

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

（4）歷史轉發次數：節點參與消息成功轉發過程的次數一定程度上體現了節點的數據轉發積極性和有效性，將節點i最近時間范圍內的成功轉發次數設為Ci，此后根據節點的轉發情況對該值進行調整。

2.3 CBOF算法設計

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

其中的Dnode-ID轉發消息的目的節點，為其他節點發布當前的競爭轉發信息，Forwarding Messages為當前待轉發的消息，Time Strap為競爭時間窗，發布競爭消息后在該時間段內接收競爭節點的信息，Reward為消息成功轉發至目的節點后，參與轉發過程的節點所獲得的相應報酬。

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

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

基于節點競爭轉發的算法基本步驟如下：

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

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

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

3 實驗仿真

3.1 仿真參數與環境設置

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

表1 參數設置

3.2 仿真結果與性能分析

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

（1）節點數量相同

圖2 交付率隨節點數量變化圖

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

圖3 傳輸延遲隨節點數量變化圖

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

圖4 路由開銷隨節點數量變化圖

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

（2）緩存空間相同

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

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

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

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

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

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

（3）運行時間相同

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

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

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

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

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

4 結語

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

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