基于模糊決策的網(wǎng)絡(luò)簇首選舉算法

丁晟皓，李小南

基于模糊決策的網(wǎng)絡(luò)簇首選舉算法

丁晟皓，李小南

（西安電子科技大學(xué)，西安 710026）

分級(jí)分簇網(wǎng)絡(luò)是目前最為常見的自組織網(wǎng)絡(luò)架構(gòu)，簇首選舉是其網(wǎng)絡(luò)管理的關(guān)鍵技術(shù)。研究比較了常用的簇首選舉算法，提出了一種基于模糊決策的復(fù)合加權(quán)簇首選舉算法。在對(duì)節(jié)點(diǎn)諸多評(píng)價(jià)因素進(jìn)行分析的基礎(chǔ)上，建立了模糊評(píng)判模型，詳細(xì)描述了算法的實(shí)現(xiàn)流程，并通過(guò)仿真驗(yàn)證了算法的適用性。

無(wú)線自組織網(wǎng)絡(luò)；簇首；加權(quán)分簇；模糊決策

0 引言

移動(dòng)自組織網(wǎng)絡(luò)（Ad Hoc網(wǎng)絡(luò)）作為一種分布式自組織的無(wú)線網(wǎng)絡(luò)，是當(dāng)前通信網(wǎng)絡(luò)領(lǐng)域研究的熱點(diǎn)之一。按照拓?fù)浣Y(jié)構(gòu)，Ad Hoc網(wǎng)絡(luò)一般分為平面網(wǎng)絡(luò)和分級(jí)網(wǎng)絡(luò)。平面網(wǎng)絡(luò)結(jié)構(gòu)簡(jiǎn)單，如圖1所示，所有節(jié)點(diǎn)地位均等，節(jié)點(diǎn)間通過(guò)路由實(shí)現(xiàn)消息交互。當(dāng)節(jié)點(diǎn)數(shù)目較多，又處于移動(dòng)狀態(tài)時(shí)，其路由維護(hù)會(huì)變得非常困難。因此，平面結(jié)構(gòu)可擴(kuò)充性較差，只適用于規(guī)模較小的Ad Hoc網(wǎng)絡(luò)。分級(jí)網(wǎng)絡(luò)是將整個(gè)網(wǎng)絡(luò)劃分為若干個(gè)簇，每個(gè)簇由一個(gè)簇首和多個(gè)簇成員組成，這些簇首還可以組成更高一級(jí)的網(wǎng)絡(luò)，因此也稱為分級(jí)分簇結(jié)構(gòu)。一種典型的分級(jí)分簇網(wǎng)絡(luò)如圖2所示。在分級(jí)網(wǎng)絡(luò)中，簇首負(fù)責(zé)維護(hù)管理簇內(nèi)各成員的資源分配和鏈路信息，同時(shí)負(fù)責(zé)簇間的通信，而簇成員只負(fù)責(zé)采集、處理和向簇首傳遞數(shù)據(jù)[1-3]。

圖1 平面網(wǎng)絡(luò)

與平面網(wǎng)絡(luò)相比，分級(jí)網(wǎng)絡(luò)具有更好的可擴(kuò)充性，其網(wǎng)絡(luò)規(guī)模不受限制，可通過(guò)增加簇的個(gè)數(shù)和網(wǎng)絡(luò)的級(jí)數(shù)來(lái)增加網(wǎng)絡(luò)成員數(shù)量。由于節(jié)點(diǎn)角色分工不同，簇成員數(shù)量雖多，但功能比較簡(jiǎn)單，從而大大降低了網(wǎng)絡(luò)的維護(hù)成本。而且各簇相對(duì)獨(dú)立，使路由信息局部化，有效減少了路由協(xié)議的開銷，因此，隨著網(wǎng)絡(luò)規(guī)模的日益擴(kuò)大，分級(jí)分簇網(wǎng)絡(luò)已成為目前最為常見的網(wǎng)絡(luò)架構(gòu)。

圖2 分級(jí)網(wǎng)絡(luò)

分級(jí)網(wǎng)絡(luò)中網(wǎng)絡(luò)管理的關(guān)鍵技術(shù)是通過(guò)分簇算法和分簇保持實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的快速部署以及拓?fù)浣Y(jié)構(gòu)變化后的動(dòng)態(tài)重建。從分級(jí)網(wǎng)絡(luò)的結(jié)構(gòu)可以看出，簇首在網(wǎng)絡(luò)的管理和通信中承擔(dān)重要的任務(wù)，是網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。因此，如何選舉簇首則成為分級(jí)網(wǎng)絡(luò)需要解決的首要問(wèn)題。

1 典型簇首選舉算法介紹

分級(jí)分簇網(wǎng)絡(luò)是將網(wǎng)絡(luò)劃分為邏輯上的若干個(gè)簇，各個(gè)簇中都有一個(gè)節(jié)點(diǎn)被選舉為簇首，是否合理的簇首選舉算法能夠決定網(wǎng)絡(luò)的總體性能。一般而言，簇首選舉需依賴具體應(yīng)用的需求、網(wǎng)絡(luò)的環(huán)境和節(jié)點(diǎn)的特征。下面介紹幾種典型的簇首選舉算法。

1）最小ID的簇首選舉算法

最小ID算法是一種簡(jiǎn)單的簇首選舉算法。在網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都分配了唯一的ID號(hào)，相鄰節(jié)點(diǎn)中選舉具有最小ID的節(jié)點(diǎn)作為簇首。并且在某些特殊情況下，現(xiàn)有簇首損毀或卸任時(shí)，可以將其職責(zé)繼續(xù)交付給其簇內(nèi)具有最小ID的成員節(jié)點(diǎn)，這種簇首選舉算法計(jì)算量小，實(shí)現(xiàn)方便，算法收斂較快，而且簇首更新的頻率較慢，維護(hù)開銷很小。但是由于該算法傾向于選舉具有較小ID的節(jié)點(diǎn)作為簇首，因而所選舉的簇首節(jié)點(diǎn)相對(duì)固定，使得這些節(jié)點(diǎn)會(huì)消耗更多的電池能量，導(dǎo)致在一定時(shí)間后它將無(wú)法繼續(xù)工作，從而縮短整個(gè)網(wǎng)絡(luò)的生存時(shí)間。

2）最大節(jié)點(diǎn)度簇首選舉算法

最大節(jié)點(diǎn)度算法不再簡(jiǎn)單地根據(jù)簇ID來(lái)選舉簇首，而是以鄰居節(jié)點(diǎn)數(shù)量來(lái)作為簇首選舉的標(biāo)準(zhǔn)。首先計(jì)算節(jié)點(diǎn)連通的鄰居節(jié)點(diǎn)數(shù)目，即節(jié)點(diǎn)度；再選舉具有最大鄰居節(jié)點(diǎn)數(shù)目的節(jié)點(diǎn)作為簇首，具體描述如下：

在個(gè)節(jié)點(diǎn)組成的集合中，每個(gè)節(jié)點(diǎn)通過(guò)消息的交互得到一個(gè)連通矩陣，如式（1）所示

式中，

定義節(jié)點(diǎn)的節(jié)點(diǎn)度如式（2）所示

若第節(jié)點(diǎn)的節(jié)點(diǎn)度滿足式（3），則該節(jié)點(diǎn)被選舉為簇首

相比最小ID的簇首選舉算法，最大節(jié)點(diǎn)度算法選出的簇首具有較好的連通性，可以減小簇內(nèi)消息轉(zhuǎn)發(fā)的資源開銷。但當(dāng)節(jié)點(diǎn)移動(dòng)速度較快時(shí)，由于簇拓?fù)浣Y(jié)構(gòu)的變化，導(dǎo)致簇首頻繁更新，維護(hù)開銷會(huì)急劇增加。

一般情況可以將最小ID算法和最大節(jié)點(diǎn)度算法結(jié)合起來(lái)進(jìn)行簇首選舉。首先根據(jù)節(jié)點(diǎn)度進(jìn)行比較，當(dāng)節(jié)點(diǎn)度相同時(shí)，再根據(jù)簇ID的大小進(jìn)行選取。這種結(jié)合在算法上雖然進(jìn)行了優(yōu)化，但在實(shí)際應(yīng)用場(chǎng)景中并沒(méi)有改善簇的穩(wěn)定性。

3）最低移動(dòng)性簇首選舉算法

為了適應(yīng)節(jié)點(diǎn)的移動(dòng)特性，提高簇結(jié)構(gòu)的穩(wěn)定性，可以根據(jù)節(jié)點(diǎn)的移動(dòng)性來(lái)選舉簇首。最低移動(dòng)性簇首選舉算法規(guī)定，節(jié)點(diǎn)的移動(dòng)性越高，其分配的權(quán)重越低，最終選舉權(quán)重最高的節(jié)點(diǎn)作為簇首。這種算法需要量化節(jié)點(diǎn)的移動(dòng)性。最簡(jiǎn)單的方法是將節(jié)點(diǎn)相對(duì)速度絕對(duì)值的時(shí)間平均作為移動(dòng)性，但這需要獲取節(jié)點(diǎn)的位置信息，不是所有的應(yīng)用環(huán)境都具備這個(gè)條件。因此最低移動(dòng)性簇首選舉算法具有一定的局限性，并且只適用于計(jì)算量小的場(chǎng)合。

4）基于能量消耗的簇首選舉算法

前面介紹的幾種簇首選舉算法中都沒(méi)有考慮負(fù)載平衡等因素，使得作為簇首的節(jié)點(diǎn)負(fù)擔(dān)較重，很容易能量耗盡。為了解決此問(wèn)題，基于能量消耗的簇首選舉算法為簇首的生存時(shí)間設(shè)定一個(gè)閾值，當(dāng)簇首節(jié)點(diǎn)承擔(dān)簇首功能的時(shí)間超過(guò)此閾值時(shí)，卸任簇首功能，并將簇首轉(zhuǎn)讓給其他符合簇首要求的節(jié)點(diǎn)。該算法使簇首的負(fù)載分布相對(duì)更為均勻，增強(qiáng)了簇的穩(wěn)定性。

5）加權(quán)簇首選舉算法

以上幾種算法中，簇首的選舉只考慮使用單一屬性作為標(biāo)準(zhǔn)。為了適應(yīng)多樣化的無(wú)線自組網(wǎng)的應(yīng)用場(chǎng)景，可以采用一種組合的加權(quán)簇首選舉算法，綜合考慮節(jié)點(diǎn)度、移動(dòng)性和能耗等多方面因素來(lái)選舉簇首。加權(quán)簇首選舉算法采用權(quán)值表示每個(gè)節(jié)點(diǎn)適合充當(dāng)簇首的程度，選擇權(quán)值最大的節(jié)點(diǎn)作為簇首，權(quán)值的計(jì)算方法如式（4）所示

加權(quán)簇首選舉算法中，每個(gè)權(quán)重系數(shù)根據(jù)具體應(yīng)用選用合適數(shù)值，并且可根據(jù)需要增加更多的變量，提高了算法適應(yīng)性。同時(shí)通過(guò)多種因素的綜合考慮，提高了分簇結(jié)構(gòu)的穩(wěn)定性。但在加權(quán)簇首選舉算法中，如何確定各屬性所占權(quán)重是個(gè)難題，同時(shí)權(quán)值的計(jì)算和存儲(chǔ)也需要額外的成本。

2 基于模糊決策的加權(quán)簇首選舉算法

從上述選舉算法的比較可以看出，由于網(wǎng)絡(luò)環(huán)境和業(yè)務(wù)需求的多樣化，加權(quán)簇首選舉算法的應(yīng)用價(jià)值十分廣泛。在傳統(tǒng)的加權(quán)簇首選舉算法中，各屬性都是用一個(gè)確切的數(shù)值表示, 并用確定的系數(shù)來(lái)表示這些確切數(shù)值的權(quán)重。但在現(xiàn)實(shí)網(wǎng)絡(luò)中,節(jié)點(diǎn)不斷移動(dòng),每個(gè)節(jié)點(diǎn)的電量也不斷變化，這些屬性很難使用常規(guī)算式表示。各權(quán)重值也是根據(jù)開發(fā)者對(duì)網(wǎng)絡(luò)環(huán)境和節(jié)點(diǎn)設(shè)備的認(rèn)知以及經(jīng)驗(yàn)進(jìn)行選取的，標(biāo)準(zhǔn)不易界定。在考慮的屬性較多時(shí), 很難給出合理的權(quán)重值分配,導(dǎo)致評(píng)價(jià)結(jié)果過(guò)于簡(jiǎn)單和主觀。

為了對(duì)各種屬性進(jìn)行綜合客觀的評(píng)價(jià),相對(duì)真實(shí)地反映出各屬性在簇首選舉中的地位，本文設(shè)計(jì)了一種基于模糊決策的簇首選舉算法，采用模糊集表示各節(jié)點(diǎn)的評(píng)價(jià)，建立模糊評(píng)價(jià)模型，從而得到評(píng)價(jià)結(jié)果。模糊決策是一種將一空間輸入映射到另一空間輸出的規(guī)則,模糊性反映事物的不確定性和不精確性,因而對(duì)動(dòng)態(tài)的自組織網(wǎng)絡(luò)有很好的 適應(yīng)性。

2.1 模糊評(píng)價(jià)模型

為了使用更恰當(dāng)?shù)哪Ｐ兔枋霾淮_定性概念，美國(guó)控制論專家Zadeh于1965年第一次提出了模糊集合的概念[6]。與只有“屬于”和“不屬于”這兩種狀態(tài)的經(jīng)典集合不同，模糊集使用隸屬度函數(shù)描述元素對(duì)集合的隸屬程度，該函數(shù)為每個(gè)元素分配一個(gè)介于0～1之間的隸屬度，以此度量各元素對(duì)集合的隸屬程度高低。

綜合評(píng)價(jià)是指使用系統(tǒng)規(guī)范的方法對(duì)多個(gè)指標(biāo)與單位建立指標(biāo)體系，對(duì)它們同時(shí)進(jìn)行評(píng)價(jià)。若使用的指標(biāo)集為模糊集，則稱為模糊評(píng)價(jià)。

對(duì)某個(gè)對(duì)象進(jìn)行綜合評(píng)價(jià)，需要考慮三個(gè)要素：

從屬性集到評(píng)價(jià)集的評(píng)價(jià)矩陣如式（5）所示

由于各屬性的重要程度不同, 因此需要進(jìn)行加權(quán)處理，權(quán)重系數(shù)用式（6）的權(quán)重矩陣表示為

將權(quán)重矩陣與評(píng)價(jià)矩陣相乘，可得到對(duì)各屬性的綜合評(píng)價(jià)矩陣，如式（7）所示

2.2 模糊決策算法

基于模糊決策的網(wǎng)絡(luò)簇首選舉算法采取綜合評(píng)價(jià)的方式，選舉得分最高的節(jié)點(diǎn)成為簇首。

首先根據(jù)網(wǎng)絡(luò)的實(shí)際情況，選取合理的評(píng)價(jià)因素。按照一般自組網(wǎng)的常用特性，本文主要考慮五個(gè)因素：節(jié)點(diǎn)度、節(jié)點(diǎn)移動(dòng)性、節(jié)點(diǎn)中心度、鏈路波動(dòng)性和節(jié)點(diǎn)剩余電量。

1）節(jié)點(diǎn)度：節(jié)點(diǎn)度是指節(jié)點(diǎn)通信范圍內(nèi)的節(jié)點(diǎn)個(gè)數(shù)，也就是節(jié)點(diǎn)的一跳鄰居個(gè)數(shù)，通過(guò)連通表獲得。

2）節(jié)點(diǎn)移動(dòng)性：為了避免頻繁的簇首改變，應(yīng)該選舉移動(dòng)速率相對(duì)較低的節(jié)點(diǎn)擔(dān)任簇首，以保持簇的穩(wěn)定性。節(jié)點(diǎn)的移動(dòng)性可通過(guò)在過(guò)去時(shí)間段內(nèi)的移動(dòng)速率平均值來(lái)衡量。

3）節(jié)點(diǎn)中心度：中心度是指與鄰居節(jié)點(diǎn)的平均距離。中心度越高，簇首與鄰居節(jié)點(diǎn)的平均距離越小，節(jié)點(diǎn)之間結(jié)構(gòu)越緊密，鏈路由于節(jié)點(diǎn)移動(dòng)發(fā)生斷裂的可能性越小，則拓?fù)浣Y(jié)構(gòu)相對(duì)較穩(wěn)定。

4）鏈路波動(dòng)性：鏈路波動(dòng)性由鏈路生存時(shí)間表示。鏈路生存時(shí)間越長(zhǎng)，波動(dòng)性越小，則網(wǎng)絡(luò)越穩(wěn)定。

5）節(jié)點(diǎn)剩余電量：剩余電量越多，節(jié)點(diǎn)生存時(shí)間越長(zhǎng)。由于簇首承擔(dān)更多的通信任務(wù)，其能耗要多于普通節(jié)點(diǎn)，因此簇首的選舉還需考慮節(jié)點(diǎn)的剩余電量情況。

圖3 節(jié)點(diǎn)度隸屬度函數(shù)

圖4 節(jié)點(diǎn)移動(dòng)性隸屬度函數(shù)

圖5 節(jié)點(diǎn)中心度隸屬度函數(shù)

圖6 鏈路波動(dòng)性隸屬度函數(shù)

圖7 節(jié)點(diǎn)剩余電量隸屬度函數(shù)

在對(duì)關(guān)鍵因素的分析基礎(chǔ)上，下一步需要確定各屬性的權(quán)重。一般情況下，權(quán)重值往往是根據(jù)用戶需求、網(wǎng)絡(luò)環(huán)境、設(shè)備特征以及過(guò)往經(jīng)驗(yàn)進(jìn)行選取，具有一定的主觀性。本文提供了一種特征向量法，能夠較為客觀地確定各項(xiàng)因素的權(quán)重，并且具有通用性。具體方法如下：

求出各個(gè)評(píng)價(jià)因素的相關(guān)系數(shù)矩陣，如式（11）所示

綜上所述，基于模糊決策的網(wǎng)絡(luò)簇首選擇算法流程如下：

2）對(duì)參與簇首選舉的全部個(gè)節(jié)點(diǎn)，根據(jù)其各屬性值，得到觀測(cè)矩陣

3）按照式（8）～式（12）計(jì)算得到權(quán)重矩陣；

4）針對(duì)任一節(jié)點(diǎn)，根據(jù)各屬性的隸屬度函數(shù)，按照?qǐng)D3～圖7計(jì)算評(píng)價(jià)矩陣

7）重復(fù)4）～6），直至遍歷全部個(gè)節(jié)點(diǎn)，得到所有節(jié)點(diǎn)的綜合評(píng)分；

8）選舉綜合評(píng)分最高的節(jié)點(diǎn)為簇首，若有多個(gè)節(jié)點(diǎn)評(píng)分相同，則其中ID號(hào)較小的成為簇首。

2.3 仿真分析

仿真場(chǎng)景設(shè)置為一個(gè)1 km×2 km的監(jiān)視區(qū)域，隨機(jī)部署一個(gè)簇內(nèi)8個(gè)節(jié)點(diǎn)以進(jìn)行仿真驗(yàn)證。以節(jié)點(diǎn)度、節(jié)點(diǎn)移動(dòng)性、節(jié)點(diǎn)中心度、鏈路波動(dòng)性和剩余能量作為評(píng)價(jià)因素，其仿真數(shù)據(jù)如表1所示。

表1 仿真數(shù)據(jù)

以表1的仿真數(shù)據(jù)為例，按照本文提出的模糊決策方法，可計(jì)算求得權(quán)重矩陣為

表2 評(píng)價(jià)結(jié)果

比較評(píng)分結(jié)果，選舉節(jié)點(diǎn)5作為簇首。

3 結(jié)語(yǔ)

本文根據(jù)自組網(wǎng)的特點(diǎn)，在分級(jí)分簇網(wǎng)絡(luò)傳統(tǒng)簇首選舉方法的基礎(chǔ)上,設(shè)計(jì)了一種基于模糊決策的簇首選舉算法。選取節(jié)點(diǎn)度、移動(dòng)性、中心度、鏈路波動(dòng)性和剩余能量作為綜合評(píng)價(jià)的關(guān)鍵因素，建立了模糊決策的數(shù)學(xué)模型，提出了各因素權(quán)重的確定方法，并詳細(xì)介紹了多種因素綜合評(píng)判的具體實(shí)現(xiàn)過(guò)程。最后通過(guò)仿真實(shí)驗(yàn), 分析驗(yàn)證了該算法的適用性。本文提出的方法能夠適合多種環(huán)境下的自組織網(wǎng)絡(luò)，確保簇首選舉的合理性和客觀性，從而提高網(wǎng)絡(luò)的整體能效。

[1] 鄭少仁，王海濤，趙志峰，等. Adhoc網(wǎng)絡(luò)技術(shù)[M]. 北京：人民郵電出版社，2005.

[2] 姚正綱，等. 一種無(wú)線鏈狀網(wǎng)絡(luò)路由算法的研究與應(yīng)用[J]. 微計(jì)算機(jī)信息，2012（1）.

[3] 李建波. 無(wú)線傳感網(wǎng)絡(luò)拓?fù)淇刂迫舾蓡?wèn)題研究[D]. 北京：中國(guó)科學(xué)技術(shù)大學(xué)，2009.

[4] 王露. 大規(guī)模無(wú)人機(jī)集群動(dòng)態(tài)網(wǎng)絡(luò)技術(shù)研究[J]. 現(xiàn)代導(dǎo)航，2022，13（5）：357-362.

[5] Zhao R，Lee H K. Fuzzy-based path planning for multiple mobile robots in unknown dynamic environment[J]. Journal of Electrical Engineering and Technology，2017，12（2）：918-925.

[6] Zadeh L A. Fuzzy sets [J]. Information and control，1965，8（3）： 338-353.

[7] ATANASSOV K T. Intuitionistic fuzzy sets [J]. Fuzzy Sets and Systems，1986，20（1）：87-96.

[8] LI X N，WANG X，LANG G M，et al. Conflict analysis based on three-way decision for triangular fuzzy information systems[J]. International Journal of Approximate Reasoning，2021，132：88-106.

[9] LI X N. Three-way fuzzy matroids and granular computing[J]. International Journal of Approximate Reasoning，2019，114：44-50.

[10] Wang Z X，Liu Y J，F(xiàn)an Z P，et al. Ranking L-R fuzzy number based on deviation degree[J]. Information Sciences，2009，179（13）：2070-2077.

[11] Bustince H，Barrenechea E，Pagola M，et al. A historical account of types of fuzzy sets and their relationships [J]. IEEE Transactions on Fuzzy Systems，2015，24（1）：179-194.

[12] 張小紅. 模糊數(shù)學(xué)與Rough集理論[M]. 北京：清華大學(xué)出版社，2013.

Cluster Head Election Algorithm Based on Fuzzy Decision

DING Shenghao, LI Xiaonan

Classified cluster network is the most common self-organized network architecture, and cluster head election is the key technology of network management. The popular election algorithm is compared and a composite weighted election algorithm based on fuzzy decision is proposed. Based on the analysis of many evaluation factors of nodes, a fuzzy evaluation model is established, and the implementation process of the algorithm is described in detail, and then the applicability of the algorithm is verified through simulation.

Wireless Self-Organizing Network; Cluster Head; Weighted Clustering; Fuzzy Decision

TP393

A

1674-7976-(2023)-05-381-06

2023-04-06。

丁晟皓（1996.05—），江蘇睢寧人，碩士，主要研究方向?yàn)槿Q策與粗糙集。