周永，岳志鵬（西華大學計算機與軟件工程學院，成都　610039）

車載自組織網絡激勵機制研究

周永，岳志鵬
（西華大學計算機與軟件工程學院，成都610039）

0　引言

社會經濟的迅速發(fā)展，使得人們的生活水平不斷提高，在城市交通領域，由于近幾年車輛數量的大量增加，造成交通安全事故不斷上升，為有效減少交通安全事故，保證人們安全出行，近幾年興起的以安全應用通信為主旨的車載自組織網絡受到了各界人士的重點關注。盡管到目前為止車載自組織網絡被大量的學者所研究，并且有很多的成果問世，例如適用于車輛網絡的路由協議、安全應用等。但是，這些研究成果都有一個前提條件，那就是他們假設車載自組織網絡之間的車輛節(jié)點都是在無私的接收和轉發(fā)數據。然而，車載自組織網絡中的各個節(jié)點不是屬于相同的個人，也不是屬于同一個組織，每個用戶會根據自身需求來盡可能節(jié)省自身的資源，即自私性。而且車輛節(jié)點會在自身利益的驅動下，會表現出盡量不去幫助需要多跳才能完成數據轉發(fā)的車輛節(jié)點，因為那樣會占用其自身的資源，如帶寬資源、計算存儲資源等。假如，大量的車輛節(jié)點都不去轉發(fā)數據，那么車輛節(jié)點就只能通過周圍一跳的其它節(jié)點或者路邊單元來完成數據的轉發(fā)那是不太現實的，那樣就不能夠實時的獲取到周圍情況，而且還不能訪問遠處的車輛，最終形成的整個網絡都是分離的，然而，在實際情況下，這樣的網絡是不存在且沒有任何意義的，更不用去分析它的性能。因此，車輛相互之間的合作問題就成了關鍵問題，也是本文最終要解決的問題。

1　激勵機制算法設計

1.1車輛節(jié)點的轉發(fā)能力

（1）車輛節(jié)點合作概率

車輛節(jié)點的合作概率指的是當車輛節(jié)點處于合作狀態(tài)時的轉發(fā)概率。為了能更好地體現出車輛當前的轉發(fā)能力，車輛間的合作問題需要以車輛節(jié)點過去的行為表現為依據，充分結合節(jié)點的歷史信息來解決。

設車輛節(jié)點的歷史活躍指數集合為Hn={H1，H2，…，Hi，…，Hn}，車輛的合作概率為Ci，則車輛節(jié)點的合作概率公式如公式（1）所示。

（2）車輛節(jié)點的轉發(fā)能力

在設計車輛節(jié)點的轉發(fā)能力時，將活躍指數歷史歸零次數考慮在內，根據每個車輛節(jié)點都是理性的，且對自己發(fā)布出來的消息不存在欺騙的情況下，若節(jié)點的歷史歸零次數越多，即被懲罰的次數越多，則該車輛節(jié)點的轉發(fā)能力會更弱，由此本文設計出了結合節(jié)點的合作概率和活躍度歸零次數的轉發(fā)能力公式。

設活躍指數歸零次數為k，車輛節(jié)點的轉發(fā)能力為pi，如公式（2）所示。

其中，RSSI為節(jié)點的信號強度。

將公式（1）代入（2）得：

通過公式（3），將車輛節(jié)點的主觀轉發(fā)概率和實際的信號強度結合起來，共同決定車輛節(jié)點的實際轉發(fā)能力，這樣既能考慮到節(jié)點的主觀轉發(fā)概率，又能考慮到車輛節(jié)點的實際轉發(fā)能力。

1.2懲罰時間

在車載網絡中，當車輛節(jié)點的活躍指數為零時，車輛節(jié)點就進入到懲罰狀態(tài)。為了有效地激勵自私節(jié)點，使其積極地參與網絡協作，在懲罰狀態(tài)下，車輛節(jié)點是不能夠獲取到其他節(jié)點的資源和服務的，除此之外，這類車輛節(jié)點必須無償的為其他節(jié)點提供自身資源服務。這里說的無償指的是為其他節(jié)點轉發(fā)數據信息時，其本身的活躍指數仍然為零，保持不變，直到懲罰時間的結束。

在設計懲罰時間長度的時候應該將車輛節(jié)點的歷史行為考慮在內。因此，本文采用的基于時間的懲罰機制的思想來源于二進制退避算法。二進制退避算法常用于解決網絡沖突的問題，防止在已經產生沖突之后，根據已有的沖突次數計算等待時間來降低再次沖突的情況發(fā)生。同樣如此，在設計基于時間的懲罰的機制時也必須考慮到同一個車輛節(jié)點再次變?yōu)樽运焦?jié)點的情況，針對同一節(jié)點多次變?yōu)樽运焦?jié)點，適當的延長其懲罰時間。因此，自私車輛節(jié)點的懲罰時間長度的公式如（4）所示。

其中，T0表示初始懲罰時間，k表示活躍度歸零次數，T表示的是第k次的懲罰時間。

1.3激勵機制方案

在選擇下一跳車輛節(jié)點時，首先不僅要考慮到車輛節(jié)點的自私性，還要將節(jié)點的客觀條件，例如通信鏈路質量等考慮在內。為了激勵車輛節(jié)點參與轉發(fā)數據包，每個車載單元都安裝有計數器，計數器用于統計車輛節(jié)點的活躍指數H和活躍指數歸零次數k，且初始值分別設置為H0>0，k=0。車輛在行駛過程中會周期性的發(fā)送信標，告知周圍節(jié)點希望參與數據包的轉發(fā)。如果某車輛發(fā)送信標超過一定時長λ，就將其對應的活躍指數遞增，當車輛發(fā)送自己的數據包和接收自己的數據包時，其對應的活躍指數遞減，當車輛實際參與數據包轉發(fā)，其活躍指數也會增加。但是，如果車輛被選為下一跳而拒絕轉發(fā)數據包時，其對應的活躍指數會直接被清零，根據前面提到的，當活躍指數為零時，這樣的節(jié)點會被判定為自私節(jié)點，立即進入懲罰期。又由于節(jié)點不能謊報自身的信息，周圍的節(jié)點通過其發(fā)送的信標可以知道這個節(jié)點為自私節(jié)點。

①激勵機制算法實現步驟

設車輛節(jié)點S發(fā)送消息給車輛節(jié)點D，激勵機制方案算法的具體實現步驟如下所示：

第一步，車輛周期性地向網絡中的周邊節(jié)點廣播信標消息，消息中主要包含自己的ID信息，坐標位置，運行速度，駛往方向和活躍指數。同時，每輛車和路邊單元都各自維護并周期性更新自己的鄰居列表，車輛節(jié)點為了能周期性的獲取到周邊鄰居車輛節(jié)點信息，車輛與車輛之間通過信標來傳遞消息，并在自己的鄰居表里添加只有一跳的鄰居的ID、活躍指數和坐標信息，最終獲得周圍網絡拓撲。

第二步，當車輛S發(fā)送數據時，根據車輛節(jié)點S和D的地理位置來獲取傳輸路徑經過的路邊單元位置信息和車輛D的位置信息，并加入到數據包頭部，車輛S通過查找自己的鄰居列表，選取駛往路徑中路邊單元方向且轉發(fā)能力最強的鄰居，將數據包傳輸給它。

第三步，收到數據包的車輛節(jié)點繼續(xù)通過第二步將數據包發(fā)送出去直到數據包到達傳輸路徑的路邊單元或附近的車輛節(jié)點。當該跳路邊單元有駛往下一跳路邊單元的車輛節(jié)點時則轉發(fā)到駛往下一跳路邊單元的車輛節(jié)點，若沒有，則直接發(fā)送到路邊單元，等待駛往下一跳路邊單元的車輛，若超時，則丟包，返回到第一步，否則轉下一步。

第四步，當路邊單元收到轉發(fā)數據后，將自己的編號和在之前的路邊單元編號從數據包頭部的傳輸路徑中去除后再轉發(fā)出去。以此類推，當最后一個路邊單元收到數據包后，路邊單元會根據位置服務器獲取當前目的節(jié)點所在位置，在這里主要是通過最近一次間隔更新的運行速度和行駛方向來預測出此時目標節(jié)點D的準確位置，繼而將消息發(fā)送給它。

②車輛節(jié)點接收數據包流程

在引入了激勵機制之后，車輛間的數據轉發(fā)行為會變得比引入之前復雜，根據本文設定的規(guī)則，處于懲罰期的車輛節(jié)點不能夠接收屬于自己的節(jié)點，因此要考慮到節(jié)點的活躍指數。以下是本文激勵機制算法下車輛節(jié)點接收數據包的流程圖，如圖1所示。

圖1　接收流程圖

從以上流程圖可以看出，車輛節(jié)點在接收數據包時具體分了四種情況，首先根據數據包的從屬來決定了數據包的不同處理。若數據包的目的節(jié)點是當前接收的車輛節(jié)點，則進一步要判斷該車輛節(jié)點此刻是否處于懲罰期，因為在懲罰期內，根據前面提到的規(guī)定，這樣的節(jié)點是不能夠接收該數據包的。反之，則接收，并要使其活躍指數遞減，因為接收自己的數據包，占用了其他節(jié)點的資源；若數據包最終要到達的車輛節(jié)點不是當前接收節(jié)點，當節(jié)點接收數據包后，如果不轉發(fā)該數據包，則活躍指數清零并立即進入懲罰狀態(tài)，反之，則更新活躍指數；當節(jié)點直接拒絕接收數據包時，則活躍指數也直接清零并進入懲罰期。

③車輛節(jié)點發(fā)送數據包流程

考慮到激勵機制，車輛節(jié)點間發(fā)送數據包較引入激勵機制之前也是更為復雜。因此，發(fā)送數據包也就不是簡單地發(fā)送數據包，這里需要將發(fā)送進行細化，必須得考慮到發(fā)送是屬于源節(jié)點發(fā)送，還是轉發(fā)。詳細的步驟如流程圖2所示。

從圖2中可以看出，根據判斷當前節(jié)點是否是數據包的源節(jié)點，將發(fā)送流程分為直接發(fā)送和轉發(fā)。如果是直接發(fā)送，即當前節(jié)點發(fā)出自身的消息時，需要判斷該車輛節(jié)點是否處于懲罰期，若處于懲罰期，則懲罰期的節(jié)點是不能夠發(fā)送自己的消息的。若不是處于懲罰狀態(tài)，根據鄰居列表獲取轉發(fā)能力最強的車輛節(jié)點作為下一跳節(jié)點，然后發(fā)出數據包，同時遞減活躍指數。如果是轉發(fā)消息，即當前節(jié)點是消息發(fā)送中的一個中繼節(jié)點時，若節(jié)點沒有轉發(fā)消息，則活躍指數清零；若節(jié)點轉發(fā)了數據信息，則和直接發(fā)送流程相似。只是，在最后需要判斷該節(jié)點狀態(tài)，如果該節(jié)點沒有處于懲罰期，則需要使其活躍指數遞增，反之，則不需要更新活躍指數，因為處于懲罰狀態(tài)的車輛節(jié)點必須無償的為其他車輛節(jié)點提供服務，直到懲罰期結束為止。

圖2　發(fā)送流程圖

2　性能分析

2.1吞吐比例分析

圖3　吞吐比率

圖4　吞吐比率

為了定向的研究車輛節(jié)點轉發(fā)概率同吞吐比率之間的關系，下面從有激勵機制情況和沒激勵機制情況來分析吞吐比率。

假設中繼車輛節(jié)點的轉發(fā)概率pi相同，轉發(fā)概率下降的梯度Δ的值相同。下面分別給出了相鄰節(jié)點吞吐比率與轉發(fā)概率在元組（m，r，n）影響下的關系。其中，r為自私影響度、n為中繼節(jié)點數和m為通信鏈路質量。

當r、n固定時，m值不同時，在有無激勵機制條件下吞吐比率變化圖，如圖3所示。

當m、n固定時，r值不同時，在有無激勵機制條件下吞吐比率的吞吐比率變化圖，如圖4所示。

圖5　吞吐比率

當m、r固定時，n值不同時，在有無激勵機制條件下吞吐比率的實驗數據和吞吐比率變化圖，如圖5所示。

根據圖3，圖4，圖5，詳細分析了m、r、n三種因素分別在有無激勵機制情況下對吞吐比率的影響，從以上分析結果可以得出，在有激勵機制條件下的吞吐比率明顯高于無激勵機制時的吞吐比率，說明本文設計的激勵機制方案能夠起到激勵機制的效果。

2.2時延分析

圖6　時延比值

圖7　時延比值

時延是研究無線網絡的重要指標之一，分析時延性能是判斷方案設計是否可行的重要方面，尤其是在車載自組織網絡中，對時延的指標相對較高。因此，下文給出了時延在本文激勵機制方案下和無激勵機制條件下的具體分析。

假設中繼車輛節(jié)點的轉發(fā)概率pi相同，Δ的值相同，下面分別給出了相鄰節(jié)點的時延比值與成功傳輸概率在元組（m，r，n）影響下的關系。

當m，r固定時，n不同時，分別給出了同等條件下有激勵機制時的時延與沒有激勵機制時時延的比值隨著轉發(fā)概率的關系圖，如圖6所示。

當r，n固定時，m不同時，分別給出了同等條件下有激勵機制時的時延與沒有激勵機制時時延的比值隨著轉發(fā)概率的關系圖，如圖7所示。

當m，n固定時，r不同時，分別給出了同等條件下有無激勵機制時時延的比值隨著轉發(fā)概率的實驗結果數據和關系圖，如圖8所示。

根據圖6，圖7，圖8，詳細分析了m、r、n三種因素分別在有無激勵機制情況下對時延的影響，從整體看來，無論如何，在同樣條件下，在有激勵機制條件下的時延肯定要比沒有激勵機制條件下的時延要低，說明本文設計的激勵機制方案能夠起到激勵機制的效果。

圖8　時延比值

3　結語

本文針對車載自組織網絡中的車輛節(jié)點因主觀表達出的自私性而不愿意積極的參與網絡協作，使得影響其他車輛節(jié)點也表現出自私行為，最終導致網絡性能嚴重下降的問題。本文提出了基于節(jié)點活躍指數的激勵機制，該激勵機制簡化了自私節(jié)點的檢測行為，當活躍指數為0時即可判定節(jié)點為自私節(jié)點，并立即進入懲罰狀態(tài)。同時采用了網絡中檢測沖突的退避算法思想設計出了基于時間的懲罰機制，將節(jié)點的活躍指數歸零次數考慮在內，用來計算懲罰的時間長度。通過對性能指標的理論分析和實驗可以知道，本文設計的激勵機制能夠真正地對網絡中的自私節(jié)點起到激勵的作用，能夠有效降低時延，提高吞吐比率。最終得出了本文設計的激勵機制方案能夠起到激勵機制的效果。

[1]Dimitrakopoulos G，Demestichas P.Intelligent Transportation System[J].IEEE Vehicular Technology Magazine，2010，5（1）.

[2]聞英友，趙博，趙宏.基于博弈理論的移動自組網激勵機制研究.Journal on Communications，2014，（4）.

[3]陸音，石進，謝立.Repeated-Game Modeling of Cooperation Enforcement in Wireless Ad Hoc Network.Journal of Software，2008，3 （19）:755-768..

[4]Buttyan L，Hubaux JP.Stimulating Cooperation in Self-Organizing Mobile Ad Hoc Networks[J].Mobile Networks and Applications，2003，8（5）:579-592.

[5]Zhong S，Chen J，Y.Yang.Sprite:a Simple，Chear-Proof，Credit-Based System for Mobile Ad Hoc Networks[C].The 21st Annual Joint Conference of the IEEE Computer and Communications Societies，2003，3:1987-1997.

[6]曲大鵬，王興偉，黃敏.移動對等網絡中自私節(jié)點的檢測和激勵機制.Journal of Software，2013，24（4）:887-889.[doi:10.3724/SP.J. 1001.2013.04290].

Vehicular Ad Hoc Network;Node Active Index;Incentive Mechanisms;Selfish Node

Research on the Incentive Mechanism of Vehicular Ad Hoc Network

ZHOU Yong，YUE Zhi-peng
（School of Computer and Software Engineering，Xihua University，Chengdu 610039）

1007-1423（2016）07-0047-06

10.3969/j.issn.1007-1423.2016.07.011

周永（1989-），男，四川廣安人，研究生，研究方向為計算機技術

2016-01-19

2016-02-19

車載自組織網絡以車輛為基本信息單元，由于車輛節(jié)點屬于不同的私人用戶或者不同的組織，車輛會因主觀因素表現出自私性，導致網絡中大量的數據包不能到達目的地，由此給網絡性能帶來很大影響。為解決車輛節(jié)點間的合作問題，提出一種基于節(jié)點活躍度的激勵機制，并通過建立吞吐率和時延模型進行性能分析，能夠真正地對網絡中的自私節(jié)點起到激勵的作用，有效降低時延，提高吞吐比率。

車載自組織網絡；節(jié)點活躍度；激勵機制；自私節(jié)點

岳志鵬（1990-），男，四川江油人，研究生，研究方向為計算機網絡

Vehicular Ad Hoc network takes vehicle as the basic information unit,however,the vehicle nodes in vehicular networks belong to private different users or different organizations,therefore,the vehicle will show selfish out of subjective factor,resulting in network large amounts of packets which cannot arrive at the destination,thus the network performance brought great adverse influence.In order to solve the problem of vehicle cooperation between nodes,proposes a method based on node active index incentive mechanism,and makes perfor-mance analysis through the establishment of throughput and delay model,which haves the real incentive effect on the network of selfish nodes,effectively reduces the delay and increasing the throughput ratio.