基于引力搜索和分?jǐn)?shù)階理論的高效路由算法

肖志良

(1.佛山職業(yè)技術(shù)學(xué)院 電子信息學(xué)院，廣東 佛山 528137；2.武漢大學(xué) 信息管理學(xué)院，湖北 武漢 430072)

0 引 言

當(dāng)前，IoT[1,2]被視為在傳感器、執(zhí)行器、手機(jī)等網(wǎng)絡(luò)對象之間進(jìn)行交互的無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)新范式[3,4]。其最大難題之一是如何提高節(jié)點(diǎn)的能量和工作壽命[5]。因此，一個(gè)高效的路由協(xié)議至關(guān)重要。在眾多路由協(xié)議中，有3類不同方法被廣泛用于節(jié)點(diǎn)聚類，即基于劃分聚類、基于優(yōu)化的聚類和基于LEACH的聚類。

基于劃分聚類有代表性的如文獻(xiàn)[6]，提出了CRT2FLACO聚類協(xié)議，該模型以蟻群優(yōu)化[7](ant colony optimization，ACO)能量均衡為基礎(chǔ)。根據(jù)經(jīng)驗(yàn)選擇設(shè)計(jì)規(guī)則。基于優(yōu)化的聚類使用較多，如Sun等[8]提出了用于WSN基于優(yōu)化的路由協(xié)議，即進(jìn)化算法的分簇路由協(xié)議(evolutionary routing-clustering protocol，ERP)。Lei等[9]提出了多粒子群免疫協(xié)同算法(MPSICA)，以實(shí)現(xiàn)智能化路由恢復(fù)方案。基于LEACH的聚類也得到了廣泛應(yīng)用，如Chen等[10]提出了一個(gè)基于聚類的協(xié)議，即LEACH改進(jìn)的多跳路由協(xié)議，以局部簇或簇頭的基站(base station，BS)的隨機(jī)旋轉(zhuǎn)在傳感器節(jié)點(diǎn)間實(shí)現(xiàn)能量負(fù)載的均勻分布。Singh等[11]提出了帶低能量自適應(yīng)聚類分層的多跳路由協(xié)議(MR-LEACH)。為延長WSN的工作壽命，MRLEACH將網(wǎng)絡(luò)分割為許多不同的聚類層。

本文主要目的是設(shè)計(jì)并開發(fā)出一個(gè)用于IoT的路由協(xié)議，即分?jǐn)?shù)階理論-引力搜索(fractional theory-gravitational search algorithm，F(xiàn)T-GSA)路由算法，其主要工作是將分?jǐn)?shù)階理論納入引力搜索算法中，以確定最優(yōu)簇頭。利用鏈路工作壽命、延遲、能量和距離來延長節(jié)點(diǎn)的工作壽命。

1 物聯(lián)網(wǎng)網(wǎng)絡(luò)模型

IoT網(wǎng)絡(luò)包括無線傳感器網(wǎng)絡(luò)(WSN)以及其它連接到互聯(lián)網(wǎng)的各種設(shè)備。基于無線傳感器網(wǎng)絡(luò)的IoT體系結(jié)構(gòu)如圖1所示。

圖1 基于WSN的IoT網(wǎng)絡(luò)的體系結(jié)構(gòu)

如圖1，基于WSN的IoT網(wǎng)絡(luò)包括一個(gè)基站或匯聚節(jié)點(diǎn)DB，簇頭HC，以及h個(gè)IoT節(jié)點(diǎn)。IoT節(jié)點(diǎn)之間的無線鏈路表示射頻通信范圍內(nèi)的直接通信。每個(gè)IoT節(jié)點(diǎn)均有一個(gè)唯一ID，且這些節(jié)點(diǎn)以分組的形式在網(wǎng)絡(luò)中形成聚類。節(jié)點(diǎn)使用簇頭機(jī)制將數(shù)據(jù)包傳輸?shù)交净騾R聚節(jié)點(diǎn)。

2 提出的算法

本文目的是設(shè)計(jì)開發(fā)出用于IoT網(wǎng)絡(luò)的高效路由協(xié)議。所提方法的原理圖如圖2所示。提出的IoT網(wǎng)絡(luò)模型包括一個(gè)基站和多個(gè)IoT節(jié)點(diǎn)。通過一個(gè)高效路由進(jìn)行數(shù)據(jù)包傳輸，以延長IoT節(jié)點(diǎn)的工作壽命。本文將鏈路工作壽命、節(jié)點(diǎn)的累積能量水平、節(jié)點(diǎn)之間的延遲擴(kuò)展和距離等多個(gè)目標(biāo)用于表述新的適應(yīng)度函數(shù)。然后，在FT-GSA算法內(nèi)嵌入這些多目標(biāo)函數(shù)，從而為使用IoT節(jié)點(diǎn)進(jìn)行能量高效的路由選擇最優(yōu)簇頭節(jié)點(diǎn)。

圖2 本文方法的原理

FT-GSA算法將應(yīng)用于PSO的分?jǐn)?shù)階理論[12]合并到GSA[13]算法中，根據(jù)時(shí)間對節(jié)點(diǎn)主體位置進(jìn)行更新，由此，通過GSA中的數(shù)學(xué)公式，基于分?jǐn)?shù)導(dǎo)數(shù)生成新的解。利用選出的簇頭節(jié)點(diǎn)將數(shù)據(jù)包傳輸至基站，以在IoT網(wǎng)絡(luò)中實(shí)現(xiàn)能量高效的路由，從而增加了網(wǎng)絡(luò)的工作壽命。下面對算法進(jìn)行簡要描述。

2.1 初始化

2.2 力與加速度

“力”表示在時(shí)間e處兩個(gè)節(jié)點(diǎn)主體之間所產(chǎn)生的力。由此，節(jié)點(diǎn)主體j在特定的時(shí)間e處作用在節(jié)點(diǎn)主體i上的力可以表示為

(1)

(2)

作用在聚類r中的節(jié)點(diǎn)主體i上的合力為網(wǎng)絡(luò)中其它節(jié)點(diǎn)主體施加在第r個(gè)組件上的力的隨機(jī)加權(quán)和

(3)

(4)

式中：mii為節(jié)點(diǎn)主體i的慣性質(zhì)量。節(jié)點(diǎn)主體在下一個(gè)時(shí)間處的速度為其當(dāng)前速度的一部分與其加速度的和。因此，節(jié)點(diǎn)主體i的速度可表示為

(5)

2.3 分?jǐn)?shù)階理論

若節(jié)點(diǎn)主體包含較重的質(zhì)量，則由于其在搜索空間移動較慢，會造成性能下降，從而產(chǎn)生開發(fā)問題。由于鄰近節(jié)點(diǎn)的更新特性，GSA算法中會出現(xiàn)探索問題。本文將分?jǐn)?shù)階理論與GSA算法進(jìn)行合并，以求解開發(fā)和探索問題。分?jǐn)?shù)階微積分主要被用于降低實(shí)施難度，并在分?jǐn)?shù)階導(dǎo)數(shù)方面提供更好的更新行為。為進(jìn)一步迭代，使用分?jǐn)?shù)階理論對節(jié)點(diǎn)主體的位置進(jìn)行更新

(6)

(7)

(8)

離散導(dǎo)數(shù)的階可被泛化為一個(gè)實(shí)數(shù)0≤α≤1。因此，上述公式可表示為

(9)

(10)

2.4 適應(yīng)度函數(shù)

在FT-GSA算法中通過適應(yīng)度函數(shù)求出引力質(zhì)量和慣性質(zhì)量。所提算法在適應(yīng)度函數(shù)中使用了4個(gè)參數(shù)，即距離、能量、延遲和鏈路壽命。若節(jié)點(diǎn)主體被考慮為簇頭，則聚類成員與該簇頭之間的距離較短。由此，將網(wǎng)絡(luò)的工作壽命最大化的適應(yīng)度函數(shù)表示為

(11)

其中，α、β、δ和η為加權(quán)參數(shù)，這些加權(quán)值總和為1。下面對式(11)的4個(gè)加權(quán)參數(shù)進(jìn)行簡單說明。第1個(gè)參數(shù)屬于節(jié)點(diǎn)之間距離的目標(biāo)函數(shù)，為了實(shí)現(xiàn)網(wǎng)絡(luò)整體壽命的最大化，其值非常小；第2個(gè)參數(shù)屬于適應(yīng)度評價(jià)中能量方面的目標(biāo)函數(shù)，為了最大化網(wǎng)絡(luò)工作壽命，該參數(shù)應(yīng)該始終較高；第3個(gè)參數(shù)用于評估延遲，以進(jìn)行簇頭選擇。延遲與聚類中成員數(shù)量成正比。為了最大化網(wǎng)絡(luò)壽命，延遲應(yīng)該較低；第4個(gè)參數(shù)為鏈路壽命，在對鏈路壽命[14](link life time，LLT)進(jìn)行預(yù)測時(shí)考慮了多個(gè)參數(shù)。每個(gè)聚類中，鏈路存在于每個(gè)IoT節(jié)點(diǎn)與其對應(yīng)的簇頭節(jié)點(diǎn)之間。LLT為每個(gè)聚類提供數(shù)據(jù)傳輸?shù)淖畲蟪掷m(xù)時(shí)間。鏈路壽命的數(shù)值越高，網(wǎng)絡(luò)工作壽命越大。

2.5 最優(yōu)解

通過分?jǐn)?shù)階理論對節(jié)點(diǎn)主體的位置進(jìn)行更新后，使用節(jié)點(diǎn)主體i的適應(yīng)度數(shù)值更新用于下一個(gè)迭代的質(zhì)量

(12)

2.6 終 止

使用適應(yīng)度函數(shù)，可以對節(jié)點(diǎn)主體的適應(yīng)度數(shù)值進(jìn)行評估。其后，重復(fù)對節(jié)點(diǎn)主體位置進(jìn)行更新，直到選出最優(yōu)簇頭。所提FT-GSA算法的偽代碼如下。即：通過節(jié)點(diǎn)之間評估出的最短路徑(單路徑或多路徑)進(jìn)行數(shù)據(jù)傳輸，以延長節(jié)點(diǎn)的工作壽命。

3 仿真結(jié)果與分析

3.1 仿真設(shè)置

IoT網(wǎng)絡(luò)和所提FT-GSA算法使用的固定參數(shù)數(shù)值見表1。FT-GSA算法的時(shí)間復(fù)雜度主要分為兩部分：貪婪算法找出主體位置的時(shí)間O(N·log2N)、分?jǐn)?shù)階理論與GSA算法合并搜素的時(shí)間O(N·Tm·MaxC)，其中N為總節(jié)點(diǎn)數(shù)量，MaxC是最大迭代數(shù)量，Tm為迭代一次所需時(shí)間。其總體復(fù)雜度為：O(N·log2N+N·Tm·MaxC)。

表1 用于仿真實(shí)驗(yàn)的固定參數(shù)值

3.2 仿真結(jié)果

所提FT-GSA算法的仿真結(jié)果如圖3所示。包括100個(gè)IoT節(jié)點(diǎn)，通過4個(gè)不同的輪數(shù)給出相對于基站的節(jié)點(diǎn)位置。圖3(a)是第一輪節(jié)點(diǎn)的初始位置。深黑色節(jié)點(diǎn)表示IoT節(jié)點(diǎn)，灰色節(jié)點(diǎn)則表示簇頭。初始時(shí)，所有節(jié)點(diǎn)的能量均相同(假定為1)。其后，使用提出的方法在第一輪中進(jìn)行簇頭選擇。該算法基于距離、能量、延遲、鏈路壽命4個(gè)因素選擇簇頭。在整個(gè)通信過程中對每個(gè)節(jié)點(diǎn)的能量進(jìn)行更新。圖3(b)是500輪后的節(jié)點(diǎn)位置示意圖。圖3(c)表示1500輪后節(jié)點(diǎn)位置示意圖。最小的黑色節(jié)點(diǎn)表示死亡節(jié)點(diǎn)，此處死亡節(jié)點(diǎn)被用于終止節(jié)點(diǎn)之間的數(shù)據(jù)傳輸。圖3(d)給出了2000輪后的死亡節(jié)點(diǎn)和簇頭節(jié)點(diǎn)的示意圖。從中看出，即使在最大輪數(shù)下，提出的FT-GSA算法依然能夠保持至少一個(gè)存活節(jié)點(diǎn)，由此驗(yàn)證了本文算法的有效性。

圖3 仿真結(jié)果

3.3 仿真結(jié)果

本文通過存活節(jié)點(diǎn)和網(wǎng)絡(luò)能量估計(jì)出能夠提高網(wǎng)絡(luò)壽命的加權(quán)常數(shù)。對照組有：與多粒子群免疫協(xié)同算法[9](MPSICA)和帶低能量自適應(yīng)聚類分層的多跳路由協(xié)議[11](MR-LEACH)。

3.3.1 基于存活節(jié)點(diǎn)的性能比較

各算法的性能比較如圖4所示。圖4(a)給出了IoT節(jié)點(diǎn)數(shù)量為100時(shí)的性能比較。在第1100輪，MPSICA和MR-LEACH的存活節(jié)點(diǎn)數(shù)量分別為17和74。而本文FT-GSA算法的存活節(jié)點(diǎn)數(shù)量則為100個(gè)。而在第2000輪，所提FT-GSA算法依然有7個(gè)存活節(jié)點(diǎn)，高于其它算法。圖4(b)給出了在200個(gè)IoT節(jié)點(diǎn)的場景性能比較。提出的FT-GSA算法在800輪得到200個(gè)存活節(jié)點(diǎn)，隨后逐漸降低。在最大輪數(shù)即第2000輪，提出的方法得到了21個(gè)存活節(jié)點(diǎn)。相比于其它方法，得到更多的存活節(jié)點(diǎn)。由此驗(yàn)證所提方法能夠增加網(wǎng)絡(luò)的工作壽命。這主要是因?yàn)楸疚姆椒ňC合考慮了能量、距離、鏈路壽命和延遲等多個(gè)目標(biāo)。通過修改適應(yīng)度函數(shù)，聚類成員與該簇頭之間的距離較短。網(wǎng)絡(luò)的工作壽命得到了最大化。而MPSICA算法通過睡眠機(jī)制對網(wǎng)絡(luò)的能耗控制進(jìn)行調(diào)整。其控制參數(shù)較多，隨著輪數(shù)增加，難以控制工作時(shí)長。MR-LEACH主要缺點(diǎn)是聚類層級必須在能量消耗最小的層次內(nèi)定義，這造成了聚類成員與簇頭變長，存活的節(jié)點(diǎn)數(shù)在輪數(shù)不高的情況下就達(dá)到了最低值。

圖4 利用存活節(jié)點(diǎn)數(shù)量進(jìn)行性能比較

3.3.2 基于網(wǎng)絡(luò)能量的性能比較

各算法在網(wǎng)絡(luò)能量方面的比較如圖5所示。圖5(a)給出了100個(gè)IoT節(jié)點(diǎn)場景下的網(wǎng)絡(luò)能量分析。當(dāng)使用750輪進(jìn)行簇頭選擇時(shí)，MPSICA和MR-LEACH的能量值分別為0.1439和0.2238，而本文算法則實(shí)現(xiàn)了0.3055的能量數(shù)值。與MPSICA和MR-LEACH相比，本文FT-GSA算法在所有輪數(shù)中的能量數(shù)值均明顯較高。圖5(b)給出了在200個(gè)IoT節(jié)點(diǎn)的場景下，輪數(shù)與歸一化網(wǎng)絡(luò)能量之間的權(quán)衡關(guān)系，其中歸一化網(wǎng)絡(luò)能量是網(wǎng)絡(luò)能量的另一種表示形式，也是一種規(guī)整化處理，即當(dāng)前能量在最大和最小能量間距中所占的比例。MPSICA算法在第一輪實(shí)現(xiàn)了0.5496的能量值，隨后逐漸下降至0.0263。所提算法則在初始時(shí)得到0.5497的能量值。當(dāng)輪數(shù)增加到2000時(shí)該能量值降低為0.0403。由此可以做出結(jié)論，與MPSICA和MR-LEACH算法相比，所提算法在所有輪數(shù)中均得到了最大的網(wǎng)絡(luò)能量。這主要是因?yàn)楸疚姆椒▽⒛芰恳蛩厍度氲竭m應(yīng)度函數(shù)中。將分?jǐn)?shù)階理論納入引力搜索算法中，使得路徑搜索加快，快速確定最優(yōu)簇頭，網(wǎng)絡(luò)能量最優(yōu)。

圖5 基于網(wǎng)絡(luò)能量的性能比較

執(zhí)行2000輪后的數(shù)值比較結(jié)果見表2。對于100個(gè)節(jié)點(diǎn)的場景，MPSICA和MR-LEACH方法得到的結(jié)果分別為0.58和0.63。而本文FT-GSA方法得出的延遲最低，數(shù)值為0.51。當(dāng)節(jié)點(diǎn)數(shù)量為200時(shí)，所提方法的鏈路壽命為0.049，而MPSICA和MR-LEACH得出的數(shù)值分別為0.035和0.039。在網(wǎng)絡(luò)能量分析中，所提FT-GSA算法在第2000輪的最低能量為0.040。由表2可知，本文FT-GSA算法在多個(gè)度量中均表現(xiàn)出優(yōu)于現(xiàn)有其它方法的性能。

表2 2000輪后各算法的性能比較

4 結(jié)束語

本文對每個(gè)IoT節(jié)點(diǎn)的能量進(jìn)行估計(jì)，以通過有效路由進(jìn)行數(shù)據(jù)包傳輸。所提算法結(jié)合了分?jǐn)?shù)階理論和引力搜索算法，以迭代的方式確定簇頭，使用了4個(gè)目標(biāo)函數(shù)，即距離、延遲、鏈路壽命和能量。通過存活節(jié)點(diǎn)數(shù)量和網(wǎng)絡(luò)能量的分析說明了本文算法可以增加存活節(jié)點(diǎn)的數(shù)量和網(wǎng)絡(luò)能量，從而能夠延長節(jié)點(diǎn)的工作壽命。未來將對IoT網(wǎng)絡(luò)參數(shù)在實(shí)際應(yīng)用中的效果，以及FT-GSA算法中4個(gè)參數(shù)的設(shè)定對網(wǎng)絡(luò)能量的影響進(jìn)行分析和研究。另外，IoT在移動端的應(yīng)用也將是重要研究內(nèi)容。