基于模糊邏輯推理系統的簇首選擇算法

朱國暉，楊 瑛

(西安郵電大學 通信與信息工程學院，陜西 西安 710121)

車聯網[1]是以車輛作為網絡中的節點進行無線通信的網絡。尤其是在路邊單元(Road Side Unit,RSU)無法接入的情況下，車輛與車輛之間的直接通信將成為網絡中數據傳輸的一種重要方式。在不考慮車輛節點與RSU進行數據傳輸的情況下，網絡中將無中心節點，所有節點地位平等，共同承擔路由與數據傳輸的功能，此時網絡結構是平面式的。在平面式網絡結構中，源節點(Source Node,SN)與目的節點(Destination Node，DN)之間存在多條路徑，節點可以選擇不同的路徑進行數據的傳輸，以減少網絡擁塞情況的發生。為了更好地提升車聯網的數據傳輸性能和網絡的可靠性，研究人員提出了采用分簇算法改善網絡性能[2-4]。

分簇算法的基本原理是將網絡中的節點根據一些規則集而聚合成為一個簇，并在簇內選擇一個節點成為該簇的簇首(Cluster Head,CH)，以便簇內和不同簇間或網絡的其余部分進行數據傳輸[5]。將作為網絡節點的車輛劃分為簇，有助于限制信道之間的競爭，通過網絡資源在空間上的復用進一步提升網絡的性能[6-8]。

由于車輛節點的快速移動性以及在節點數量較多的情況下，較大的路由開銷以及網絡拓撲的快速變化將會使得節點之間的簇結構變得不穩定，網絡的可擴展性變差。針對該問題，采用適當的分簇算法對網絡進行分層，使處于不同層的節點肩負起不同的職責，有效對網絡進行擴展，并且在網絡節點數量較多的情況下，減少信息冗余。因此，有效降低因選擇簇首和在高動態性和快速變化的網絡拓撲中維護所有簇成員過程中所帶來的額外網絡開銷[9]是分簇算法中的關鍵問題。

早期提出的分簇算法有最小標識優先算法和最大連接度優先算法，其均以單個因素作為簇首選擇的標準，性能較差。隨后，文獻[10-11]對這兩個基本算法進行了改進，更加符合不同的場景需求，但固定選擇一些因素作為其簇首選擇的衡量標準，在一定程度上影響了節點成為備選簇首的概率。目前，已有的關于節點分簇的算法，如文獻[12]提出的簇首選擇算法沒有考慮車輛節點在網絡中所處位置信息的變化對簇結構的影響。基于三角模糊數的簇首選擇算法[13]通過預測車輛節點的加速度完成對簇結構的劃分，考慮的因素較為單一。文獻[14]從降低基站負載的角度提出了一種分布式聚類算法和基于進化博弈論的簇首選舉算法，未考慮車輛節點的運動特性。基于移動性的穩定聚類方法[15]利用車輛節點的速度、方向以及鏈路質量等度量用于簇首選擇，但并未考慮到節點在網絡中的鄰居環境對簇結構穩定性的影響。文獻[16]考慮了節點的信息，但節點無運動屬性。

考慮到車輛節點所處的網絡環境，及在實際情況中節點的運動特性，擬提出一種基于模糊邏輯推理系統的簇首選擇算法。利用模糊邏輯推理系統，定義語言規則，綜合考慮車輛節點在網絡中的相對速度、相對鄰居節點數與相對中心度，確定每一個節點成為簇首的優先級，從而選擇較為適合的節點成為簇首并形成簇結構。

1 基于模糊邏輯的分簇算法

1.1 層次網絡模型

車輛節點與路邊基礎設施構成的車聯網應用場景如圖 1所示。在網絡中，車輛作為節點，沒有功能上的不同。

圖1 車聯網應用場景

為了提高網絡的可擴展性，需要對網絡進行分層處理，將原本處于同一平面的節點進行層次的劃分，選出能夠承擔不同作用的節點。網絡分層示意圖如圖 2所示。

圖2 網絡分層示意圖

圖2中的底層表示平面網絡的底層結構，節點之間不做區分，相互之間根據需求進行數據的傳輸。中間層代表對節點進行了初步劃分，在傳輸數據時，不再是從SN到DN進行一跳或多跳的直接傳輸，而是從SN將數據先傳輸至自己所在簇的簇首節點，再由簇首節點將數據傳輸至DN所在簇的簇首，最終到達DN。最頂層表示在不同區域選出最適合成為簇首的節點。

1.2 基于模糊邏輯的簇首選擇算法

在分簇路由算法中，簇首的產生是簇形成的基礎。為了形成一個較穩定的簇結構，盡力降低單位時間內簇的拆散與重組的次數，分別從節點的運動角度、位置角度和鄰居環境角度出發，考慮節點的相對速度(rel-V)、相對中心度(rel-C)和相對鄰居節點(rel-N)數等3個因素，通過模糊推理與解模糊化過程，得到每一個節點成為簇首的優先級，最終選擇出最適合成為簇首的節點。

1.2.1 模糊邏輯推理系統

簇首的選擇原則是基于模糊邏輯。常見的模糊推理系統可分為純模糊邏輯系統、Sugeno型與Mamadani型等3種。其中，純模糊邏輯系統是其他類型模糊邏輯系統的核心部分，其提供了一種將語言信息量化的方法,并且是在一般模糊邏輯的原則下利用這類語言信息的一般化模型。純模糊邏輯系統可以看作為一個映射關系，輸入模糊集A通過模糊邏輯系統中的模糊規則庫與模糊推理得到輸出模糊集B，如圖 3所示。一般化模糊邏輯系統如圖 4所示。

圖3 純模糊邏輯系統

Mamadani型模糊推理算法采用if/then規則定義輸入與輸出之間的模糊關系，如ifxisAandyisBthenzisC。其中，x和y為輸入語言變量，A和B為推理前件的模糊集合，z為輸出語言變量，C為模糊規則的后件。將已定義的模糊規則作用于輸入語言變量，通過模糊推理將輸出合并成模糊集合，采用相應的解模糊化方法，最終得到精確的輸出。較為常用的解模糊化方法有質心法、面積重心法和極大平均法等。

Sugeno模型將解模糊化與模糊推理相結合，輸出量為精確量。其中，精確輸入量模糊化和模糊邏輯運算過程與Mamadani型相同，但輸出隸屬度函數的形式與Mamdani型存在差異。舉例說明，一階Sugeno型模糊規則的形式為ifxisAandyisBthenz=px+qy+r。其中：x和y為輸入語言變量；A和B為推理前件的模糊集合；z為輸出語言變量；p、q和r為常數。由于高階數的Sugeno模型增加了復雜性，性能的改善效果并不是很好，故很少使用。

1.2.2 模糊邏輯輸入變量

將車輛作為網絡中的節點，節點的相對速度、相對中心度和相對鄰居節點數等3個變量的表示如下。

1)節點的相對速度。從運動角度考慮，假設某區域內共有n個節點，節點i的速度為vi，則相對速度為

對vr,i結果進行正規化，使其值映射到[0,1]區間之內，并用Vr,i表示正規化后的節點的相對速度，即

2)節點的相對中心度。從節點所處的位置角度進行考慮，相對中心度表示為

式中，xi與yi分別表示節點i的x軸坐標與y軸坐標。正規化后的節點的相對中心度表示為

3)節點的相對鄰居節點數。從鄰居環境角度進行考慮，將某節點的鄰居節點bi定義為在該節點通信范圍內的所有節點，則網絡中節點的相對鄰居節點數表示為

1.2.3 變量的模糊化與模糊規則

為節點的相對速度、相對中心度和相對鄰居節點數等3個輸入參數選擇語言變量，并為其匹配隸屬度函數。語言變量分為不同的等級，節點的相對速度={very low,low,middle,high}，節點的相對鄰居節點數={low,middle,high}，節點的相對中心度={very few,few,many,very many}。隸屬度函數選擇三角形函數與梯形函數，3個輸入參數的隸屬度函數如圖5所示。

圖5 輸入參數的隸屬度函數

根據if/then語言規則，定義了48條模糊規則，如表1所示。

表1 模糊規則庫

續表1 模糊規則庫

系統輸出為節點成為簇首的概率，規定為{very low,low,little low,middle,little high,high,very high}7個等級，對節點進行成為簇首優先級的劃分，如圖 6所示。

圖6 輸出隸屬度函數

同一個輸入參數可對應兩個不同的隸屬度函數，得到不同的模糊值，即一個輸入可同時適用于多個模糊規則。利用Min-Max決策方法將所有規則組合出的模糊結果集合并，在該方法中，將輸入值中的最小值作為每條規則的輸出值，在組合不同規則的結果時，將同規則下最大的數值作為該規則的最終值。

例如，假設某節點的相對運動速度rel-V為0.25，對應的模糊語言變量的隸屬度為{very low:0.75,low:0.25,middle:0,high:0 }。相對鄰居節點數rel-N的值為0.3，對應的模糊語言變量的隸屬度為{very few:0.5,few:0.5,many:0,very many:0}。相對中心度rel-C的值為0.5，對應的模糊語言變量的隸屬度為{low:0,middle:1,high:0}。在表1中進行查找，其分別對應“規則17”“規則18”“規則21”“規則22”，則該節點的相對運動速度為{very low}的隸屬度為0.5，相對鄰居節點數{very few}的隸屬度為0.5以及相對中心度{middle}的隸屬度為1。對應“規則17、18、21、22”并考慮Min-Max決策方法，可得到該節點成為簇首的優先級集合為{very low:0.5,low:0.5,little low:0.25}，其他對應規則整理如圖 7所示。

圖7 Min-Max決策方法示意圖

以Min-Max決策方法給出所有模糊的結果，利用重心法進行解模糊化運算，形成最后的精確輸出值為

(1)

式中：x表示隸屬度函數的橫軸；f(x)表示隸屬度函數集。計算不同隸屬函數對應的簇首概率，通過式(1)最終得到該節點能夠稱為簇首的可能的概率值。

2 模型仿真與性能分析

利用Matlab仿真軟件對基于模糊邏輯推理系統的簇首選擇算法的性能進行仿真，在不同的車輛行駛速度與車輛密度場景下，計算簇首生存時間，并與文獻[12]算法和文獻[13]算法進行對比。

2.1 簇頭選擇算法模型

簇頭選擇算法的仿真結果如圖8所示。其中，圖8(a)表示從節點相對速度和相對鄰居節點數這兩個角度考慮節點成為簇首的優先級的關系。隨著節點相對速度和相對鄰居節點數隸屬度值的增加，節點成為簇首的概率也隨之增加。圖8(b)表示從節點相對運動速度和相對中心度這兩個角度考慮節點成為簇首優先級的關系。

圖8 簇頭選擇算法模型仿真結果

2.2 性能分析

為了測試算法的有效性，分別對比所提算法、文獻[12]算法和文獻[13]算法等3種算法在不同車輛密度與車輛行駛速度的情況下，對簇穩定性的影響。設定每次仿真時間為500 s，共仿真20次，取平均值作為最終的仿真數據。不同車輛密度即交通流密度對簇結構穩定性影響的仿真結果如圖9所示。

圖9 車輛密度對簇穩定性的影響

由圖9可以看出，隨著車輛密度的增大，使得車輛之間的間距變小，促進了簇結構的穩定性，因此3種算法均表現出簇首的平均生存時間在逐漸延長。相對而言，所提算法對于維持簇首的平均生存時間更為有效，這是因為在選擇簇首時，對模糊規則庫的劃分更加詳細，從車輛的實際運動場景出發考慮，所選擇出的節點在運動角度更加適合成為簇首。

仿真過程中的車輛行駛速度服從正態分布，車速范圍為30～120 km/h。不同的車輛行駛速度對簇結構穩定性影響的仿真結果如圖10所示。

圖10 車輛行駛速度對簇穩定性的影響

由圖10可以看出，隨著車輛行駛速度的增加，簇首平均生存時間隨之減少，這是因為隨著車速范圍的增加，車輛速度的分布會逐步分散，網絡拓撲變化加劇。相比之下，所提算法較其他兩種算法，能夠提升簇首平均生存時間，其原因在于選擇簇首時對實際場景中的車輛行駛速度進行了詳細的劃分，因此從運動角度方面來講，這樣選擇出來的節點更適合成為簇首。

通過簇結構的拆分重組的流動性定義簇結構的穩定性。一個簇的結構越穩定，越不容易被拆分重組，簇整體維持的時間也就越長。3種算法的簇穩定性對比如圖11所示。可以看出，在車輛不同流動率情況的比較下，所提算法具有更好的穩定性，這是因為該算法在進行簇首選擇時更加著重的考慮了車輛節點所處的環境，考慮了鄰居節點數量與節點所處的地理位置。

圖11 簇穩定性的對比

3 結語

基于模糊邏輯推理系統的簇首選擇算法將各節點相互平等的平面網絡進行邏輯上的層次劃分，提高了網絡的擴展性，并在層次網絡中將節點分為簇首節點與非簇首節點，減少了網絡中由于節點未分工所帶來的的信息冗余所導致資浪費的情況。簇首節點的選擇分別從運動角度、位置角度和環境角度等3個方面綜合考慮，利用模糊邏輯推理系統，選擇參數最接近網絡平均值的節點成為簇首。仿真結果表明，所提算法較其他兩種算法，進一步提升了簇首的平均生存時間，增加了簇結構的穩定性。