基于模糊邏輯推理系統(tǒng)的簇首選擇算法

朱國暉，楊 瑛

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

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

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

由于車輛節(jié)點的快速移動性以及在節(jié)點數(shù)量較多的情況下，較大的路由開銷以及網(wǎng)絡(luò)拓撲的快速變化將會使得節(jié)點之間的簇結(jié)構(gòu)變得不穩(wěn)定，網(wǎng)絡(luò)的可擴展性變差。針對該問題，采用適當?shù)姆执厮惴▽W(wǎng)絡(luò)進行分層，使處于不同層的節(jié)點肩負起不同的職責，有效對網(wǎng)絡(luò)進行擴展，并且在網(wǎng)絡(luò)節(jié)點數(shù)量較多的情況下，減少信息冗余。因此，有效降低因選擇簇首和在高動態(tài)性和快速變化的網(wǎng)絡(luò)拓撲中維護所有簇成員過程中所帶來的額外網(wǎng)絡(luò)開銷[9]是分簇算法中的關(guān)鍵問題。

早期提出的分簇算法有最小標識優(yōu)先算法和最大連接度優(yōu)先算法，其均以單個因素作為簇首選擇的標準，性能較差。隨后，文獻[10-11]對這兩個基本算法進行了改進，更加符合不同的場景需求，但固定選擇一些因素作為其簇首選擇的衡量標準，在一定程度上影響了節(jié)點成為備選簇首的概率。目前，已有的關(guān)于節(jié)點分簇的算法，如文獻[12]提出的簇首選擇算法沒有考慮車輛節(jié)點在網(wǎng)絡(luò)中所處位置信息的變化對簇結(jié)構(gòu)的影響?；谌悄：龜?shù)的簇首選擇算法[13]通過預測車輛節(jié)點的加速度完成對簇結(jié)構(gòu)的劃分，考慮的因素較為單一。文獻[14]從降低基站負載的角度提出了一種分布式聚類算法和基于進化博弈論的簇首選舉算法，未考慮車輛節(jié)點的運動特性?；谝苿有缘姆€(wěn)定聚類方法[15]利用車輛節(jié)點的速度、方向以及鏈路質(zhì)量等度量用于簇首選擇，但并未考慮到節(jié)點在網(wǎng)絡(luò)中的鄰居環(huán)境對簇結(jié)構(gòu)穩(wěn)定性的影響。文獻[16]考慮了節(jié)點的信息，但節(jié)點無運動屬性。

考慮到車輛節(jié)點所處的網(wǎng)絡(luò)環(huán)境，及在實際情況中節(jié)點的運動特性，擬提出一種基于模糊邏輯推理系統(tǒng)的簇首選擇算法。利用模糊邏輯推理系統(tǒng)，定義語言規(guī)則，綜合考慮車輛節(jié)點在網(wǎng)絡(luò)中的相對速度、相對鄰居節(jié)點數(shù)與相對中心度，確定每一個節(jié)點成為簇首的優(yōu)先級，從而選擇較為適合的節(jié)點成為簇首并形成簇結(jié)構(gòu)。

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

1.1 層次網(wǎng)絡(luò)模型

車輛節(jié)點與路邊基礎(chǔ)設(shè)施構(gòu)成的車聯(lián)網(wǎng)應(yīng)用場景如圖 1所示。在網(wǎng)絡(luò)中，車輛作為節(jié)點，沒有功能上的不同。

圖1 車聯(lián)網(wǎng)應(yīng)用場景

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

圖2 網(wǎng)絡(luò)分層示意圖

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

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

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

1.2.1 模糊邏輯推理系統(tǒng)

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

圖3 純模糊邏輯系統(tǒng)

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

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

1.2.2 模糊邏輯輸入變量

將車輛作為網(wǎng)絡(luò)中的節(jié)點，節(jié)點的相對速度、相對中心度和相對鄰居節(jié)點數(shù)等3個變量的表示如下。

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

對vr,i結(jié)果進行正規(guī)化，使其值映射到[0,1]區(qū)間之內(nèi)，并用Vr,i表示正規(guī)化后的節(jié)點的相對速度，即

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

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

3)節(jié)點的相對鄰居節(jié)點數(shù)。從鄰居環(huán)境角度進行考慮，將某節(jié)點的鄰居節(jié)點bi定義為在該節(jié)點通信范圍內(nèi)的所有節(jié)點，則網(wǎng)絡(luò)中節(jié)點的相對鄰居節(jié)點數(shù)表示為

1.2.3 變量的模糊化與模糊規(guī)則

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

圖5 輸入?yún)?shù)的隸屬度函數(shù)

根據(jù)if/then語言規(guī)則，定義了48條模糊規(guī)則，如表1所示。

表1 模糊規(guī)則庫

續(xù)表1 模糊規(guī)則庫

系統(tǒng)輸出為節(jié)點成為簇首的概率，規(guī)定為{very low,low,little low,middle,little high,high,very high}7個等級，對節(jié)點進行成為簇首優(yōu)先級的劃分，如圖 6所示。

圖6 輸出隸屬度函數(shù)

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

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

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

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

(1)

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

2 模型仿真與性能分析

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

2.1 簇頭選擇算法模型

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

圖8 簇頭選擇算法模型仿真結(jié)果

2.2 性能分析

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

圖9 車輛密度對簇穩(wěn)定性的影響

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

仿真過程中的車輛行駛速度服從正態(tài)分布，車速范圍為30～120 km/h。不同的車輛行駛速度對簇結(jié)構(gòu)穩(wěn)定性影響的仿真結(jié)果如圖10所示。

圖10 車輛行駛速度對簇穩(wěn)定性的影響

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

通過簇結(jié)構(gòu)的拆分重組的流動性定義簇結(jié)構(gòu)的穩(wěn)定性。一個簇的結(jié)構(gòu)越穩(wěn)定，越不容易被拆分重組，簇整體維持的時間也就越長。3種算法的簇穩(wěn)定性對比如圖11所示?？梢钥闯?，在車輛不同流動率情況的比較下，所提算法具有更好的穩(wěn)定性，這是因為該算法在進行簇首選擇時更加著重的考慮了車輛節(jié)點所處的環(huán)境，考慮了鄰居節(jié)點數(shù)量與節(jié)點所處的地理位置。

圖11 簇穩(wěn)定性的對比

3 結(jié)語

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