肖志良

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

0 引 言

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

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

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

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

2 提出的算法

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

圖2 本文方法的原理

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

2.1 初始化

2.2 力與加速度

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

(1)

(2)

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

(3)

(4)

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

(5)

2.3 分數(shù)階理論

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

(6)

(7)

(8)

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

(9)

(10)

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

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

(11)

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

2.5 最優(yōu)解

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

(12)

2.6 終 止

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

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

3.1 仿真設(shè)置

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

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

3.2 仿真結(jié)果

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

圖3 仿真結(jié)果

3.3 仿真結(jié)果

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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