智能家居中的網(wǎng)絡(luò)路由改進(jìn)算法研究①

朱麗華, 林 平

(池州職業(yè)技術(shù)學(xué)院,安徽 池州 247000)

0 引 言

智能家居系統(tǒng)是以住宅為平臺(tái),利用計(jì)算機(jī)技術(shù)、網(wǎng)絡(luò)通信技術(shù)、綜合布線技術(shù)、傳感器技術(shù)、安防技術(shù)等打造高效、舒適、安全、智能的人文居住環(huán)境[1]。在智能家居中,所有的家庭硬件設(shè)備都基于無線傳感器網(wǎng)絡(luò)[2]的搭建而連接的,在搭建網(wǎng)絡(luò)時(shí),其路由算法相關(guān)的分析結(jié)果,和網(wǎng)絡(luò)運(yùn)行成本密切相關(guān),并且影響網(wǎng)絡(luò)效率等問題,因而算法研究極為受關(guān)注[3,4]。路由算法作為智能家居網(wǎng)絡(luò)的核心問題,直接影響了網(wǎng)絡(luò)的服務(wù)質(zhì)量和用戶的體驗(yàn)感。

1 網(wǎng)絡(luò)路由優(yōu)化算法

網(wǎng)絡(luò)路由協(xié)議常用的度量一般包括以下6個(gè)方面[5]:路徑長度(又稱為跳數(shù));可靠性;時(shí)延;帶寬;負(fù)載;通信開銷。一直以來,研究人員在網(wǎng)絡(luò)路由算法方面做了大量的研究工作,也獲得相應(yīng)的成果。如N.R. Wankhade[6],Huang C F[7]研究得到了免疫克隆算法,模擬具有免疫系統(tǒng)的生物在細(xì)菌入侵的過程中自身免疫細(xì)胞對抗原做出免疫并產(chǎn)生抗體的過程,將網(wǎng)絡(luò)路由上一次計(jì)算的最有路徑進(jìn)行保存,在下一次的計(jì)算過程中自動(dòng)以上一次的計(jì)算結(jié)果為約束條件進(jìn)行重新選路,大大提高了計(jì)算速度,但是全局搜索能力并不理想。P. Tian[8]等學(xué)者按照牛頓下山法,改進(jìn)提升了克隆免疫算法,以獲得更為優(yōu)異的全局搜索性能,不過計(jì)算效率明顯下降。王莉[9]在其研究中,則按照蟻群算法,對網(wǎng)絡(luò)路由技術(shù)進(jìn)行了分析,不過出現(xiàn)了局部最優(yōu)化的問題。文獻(xiàn)[10]通過對蟻群算法的深入研究,分析了蟻群算法在網(wǎng)絡(luò)路由協(xié)議中的應(yīng)用,建立了基于蟻群算法的模型,優(yōu)化了網(wǎng)絡(luò)路由的路徑,但忽略了網(wǎng)絡(luò)的費(fèi)用問題。文獻(xiàn)[11]提出一種優(yōu)化的蟻群算法,并建立了帶約束的網(wǎng)絡(luò)模型,雖然優(yōu)化了網(wǎng)絡(luò)服務(wù)質(zhì)量,但該蟻群算法增加了網(wǎng)絡(luò)負(fù)載,計(jì)算復(fù)雜度也比較高。在無線傳感器網(wǎng)絡(luò)中,網(wǎng)絡(luò)路由協(xié)議不僅要保證網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的信息傳輸準(zhǔn)確、高效和穩(wěn)定,傳輸路徑還要滿足通信開銷損耗小的條件[12]。Si J[13]等人將BFA(Bacterial Foraging Algorithm,細(xì)菌覓食算法)應(yīng)用到計(jì)算機(jī)網(wǎng)絡(luò)中的路由問題中,經(jīng)比較,細(xì)菌覓食算法在精度和計(jì)算速度上優(yōu)于傳統(tǒng)算法。

2 算法思想

通過對已有的研究成果分析,傳統(tǒng)、單一的算法應(yīng)用在網(wǎng)絡(luò)路由算法在通信開銷、可靠性、計(jì)算效率等方面均達(dá)不到理想效果。通過對細(xì)菌覓食算法、免疫算法、蟻群算法和BFA等深入分析研究,結(jié)合了融合半解析解的內(nèi)容[14],就算法的具體操作步驟進(jìn)行了分析,得到了GFBA算法技術(shù),該算法在細(xì)菌的趨向性、復(fù)制、遷移三個(gè)操作環(huán)節(jié)進(jìn)行了重新的整合和調(diào)整,遷移的步長值可以隨著計(jì)算的進(jìn)行而改變,用免疫算法(generate and test)代替BFA的復(fù)制操作環(huán)節(jié),在遷移操作環(huán)節(jié)中,對適應(yīng)度最高的個(gè)體被驅(qū)散的概率進(jìn)行調(diào)整。最后利用GFBA算法,建立網(wǎng)絡(luò)模型,并針對路由優(yōu)化問題進(jìn)行實(shí)驗(yàn)仿真,從計(jì)算速度、全局搜索能力、計(jì)算精度方面驗(yàn)證GFBA算法對于網(wǎng)絡(luò)路由問題的適用性和優(yōu)越性。

一般BFA算法里如果其隨機(jī)數(shù)要比遷移概率更低,就能完成細(xì)菌遷移,而遷移的目的是為了避免出現(xiàn)局部最優(yōu)解問題。按照這種處理方法,會(huì)影響全部細(xì)菌,具有良好適應(yīng)性的細(xì)菌,基本都能完成遷移。GFBA算法進(jìn)行遷移時(shí),適應(yīng)性最理想的細(xì)菌個(gè)體,驅(qū)散概率是零,而如果該參數(shù)能達(dá)到,就能讓搜索效率提升。

3 算法實(shí)現(xiàn)

基于算法思想,對于該算法的具體步驟如圖1所示。

圖1 GFBA算法操作步驟

4 實(shí)驗(yàn)仿真

4.1 拓?fù)淠Ｐ?/h3>

研究該類模型時(shí),其拓?fù)鋱D所含的n個(gè)節(jié)點(diǎn)都能通過對應(yīng)的幾率可通過下面的式子進(jìn)行求解:

(1)

式(1)中,l(p,q)為網(wǎng)絡(luò)拓?fù)鋱D中兩點(diǎn)間的歐式距離;L為網(wǎng)絡(luò)拓?fù)鋱D最大的邊長;α,β為大于零小于1的兩個(gè)實(shí)數(shù):控制網(wǎng)絡(luò)拓?fù)鋱D中的邊的數(shù)量,控制網(wǎng)絡(luò)拓?fù)鋱D中的短鏈路的數(shù)量。其對應(yīng)的區(qū)域范圍大小是200×200,50個(gè)節(jié)點(diǎn)和100個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)鋱D,具體如圖2、圖3所示。

圖2 50節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)鋱D

圖3 100節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)鋱D

圖2,3中方形節(jié)點(diǎn)為組播源,圓形節(jié)點(diǎn)為組播。

4.2 GFBA仿真結(jié)果

對于上面所得的拓?fù)淠Ｐ?可利用GFBA算法求解計(jì)算,如圖4和圖5所示,黑色粗線為組播轉(zhuǎn)發(fā)樹。

圖4 50節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)鋱D計(jì)算結(jié)果

圖5 100節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)鋱D計(jì)算結(jié)果

4.3 結(jié)果分析

針對GFBA算法里細(xì)菌個(gè)數(shù)、組播樹費(fèi)用值存在的關(guān)聯(lián)性進(jìn)行分析,可基于各個(gè)數(shù)細(xì)菌來求解50個(gè)、100個(gè)節(jié)點(diǎn)隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ?最終結(jié)果則為得到的數(shù)據(jù)均值,具體如圖6所示。

圖6 細(xì)菌的數(shù)量和組播樹費(fèi)用值的關(guān)系

圖7 細(xì)菌的數(shù)量和收斂時(shí)間的關(guān)系

如圖6所示,當(dāng)細(xì)菌個(gè)數(shù)小于19的時(shí)候,細(xì)菌數(shù)量的增加可以大幅度降低組播樹費(fèi)用,說明在這一階段,由于細(xì)菌較少,GFBA算法對應(yīng)的解也較少,其搜素最優(yōu)解的范圍很小,容易遺漏較小的值。當(dāng)細(xì)菌個(gè)數(shù)大于19的時(shí)候,細(xì)菌數(shù)量的增加不可以大幅度降低組播樹費(fèi)用,說明在這一階段,由于細(xì)菌已然足夠,GFBA算法對應(yīng)的解也較多,其搜索最優(yōu)解的范圍很廣,容易找到最小的值。組播樹費(fèi)用、細(xì)菌個(gè)數(shù)見的關(guān)聯(lián)性,以下面的數(shù)值來表達(dá):

c=3999.387-486.792m+28.268m2-

0.656m3+0.002m4-0.000001m6+

0.00012m5-322.52cosm

(2)

式(2)中 ,c為組播樹費(fèi)用;m為細(xì)菌個(gè)數(shù)。

為探究GFBA算法中,細(xì)菌的數(shù)量和收斂時(shí)長見存在的關(guān)聯(lián)性,通過各規(guī)模的細(xì)菌個(gè)數(shù),求解50個(gè)、100個(gè)節(jié)點(diǎn)隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ?最終結(jié)果則為得到的數(shù)據(jù)均值,具體如圖7所示。

根據(jù)圖6,7來看,細(xì)菌不足23個(gè)的情況下,其數(shù)量越多,那么收斂時(shí)長受到的影響較小,說明在這一階段,由于細(xì)菌較少,GFBA算法的計(jì)算量也較小,容易找到所處情形下的最優(yōu)解。當(dāng)細(xì)菌個(gè)數(shù)大于23的時(shí)候,細(xì)菌數(shù)量的增加大幅度增加了收斂時(shí)間,說明在這一階段,由于細(xì)菌數(shù)目增加,GFBA算法對應(yīng)的解也較多,其搜素最優(yōu)解的范圍很廣,收斂難度也增加。組播樹費(fèi)用和細(xì)菌數(shù)量的關(guān)聯(lián)性可以表示成式(3):

t=-3576.263027036935-

734.2037534473963cosm+

20.4207599922332cotm+

1424.4592856578956lnm+

566.7544407805706secm

(3)

式(3)中,t為收斂時(shí)間(ms);m為細(xì)菌個(gè)數(shù)。

為對GFBA算法性能進(jìn)行分析,了解其優(yōu)勢、適用性,也就是證明以下圖示內(nèi)容的正確性,可通過不同的算法來求解拓?fù)淠Ｐ唾M(fèi)用、收斂時(shí)長,也就是得到下面的圖示結(jié)果,所應(yīng)用的算法包括了遺傳算法計(jì)、免疫克隆算法等。

圖8 不同算法節(jié)點(diǎn)數(shù)量和費(fèi)用值的關(guān)系

圖9 各算法節(jié)點(diǎn)個(gè)數(shù)、收斂時(shí)長關(guān)聯(lián)性

如圖8所示,細(xì)菌數(shù)量越多,則費(fèi)用也相對更高,本文利用GFBA算法得到的結(jié)果整體成本在隨著節(jié)點(diǎn)數(shù)目增加的過程中,總體上要比其他算法計(jì)算得到的結(jié)果更低,說明提出的GFBA算法的全局搜索能力和收斂精度都高于免疫克隆算法、蟻群算法、傳統(tǒng)細(xì)菌覓食算法、遺傳算法。整體而言,算法提出的GFBA計(jì)算而得的費(fèi)用要比其他算法更低,和免疫克隆算法、蟻群算法、傳統(tǒng)細(xì)菌覓食算法、遺傳算法比較來看,下降了5.78054%,8.49318%,10.6%,9.10569%。

如圖9所示,細(xì)菌數(shù)量越多,收斂的時(shí)間也就越長,并且增大的幅度越來越大,利用GFBA算法整體時(shí)間成本隨著節(jié)點(diǎn)數(shù)目增加的過程中,要比免疫克隆算法、蟻群算法、傳統(tǒng)細(xì)菌覓食算法、遺傳算法計(jì)算而得的收斂時(shí)間更短,說明提出的GFBA算法的計(jì)算效率高。綜上所述,提出的GFBA算法計(jì)算而得的收斂時(shí)間和免疫克隆算法相比,減小了5.82%;和蟻群算法相比,減小了9.02%;和傳統(tǒng)細(xì)菌覓食算法相比,減小了14.06%;和遺傳算法求解而得的收斂時(shí)間低了14.12%。

5 結(jié) 語

針對在智能家居系統(tǒng)網(wǎng)絡(luò)研究中,提出一種網(wǎng)絡(luò)節(jié)點(diǎn)路由GFBA算法,該算法。在BFA、融合免疫算法(Generate and Test)基礎(chǔ)上,又融合了半解析解的相關(guān)思想。并針對50節(jié)點(diǎn)和100節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ瓦M(jìn)行計(jì)算,驗(yàn)證GFBA的收斂能力。此外,通過對50網(wǎng)絡(luò)節(jié)點(diǎn)和100網(wǎng)絡(luò)節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ瓦M(jìn)行計(jì)算而得的收斂時(shí)間和費(fèi)用進(jìn)行研究,發(fā)現(xiàn)細(xì)菌的數(shù)量,在不足19的情況下,GFBA所得解數(shù)量相對少,覆蓋面不全。反之,只要細(xì)菌數(shù)量達(dá)到一定量,那么這個(gè)算法所得解也相對多,覆蓋面更廣。最后,提出的GFBA算法的計(jì)算效率明顯高于免疫克隆算法、蟻群算法、傳統(tǒng)細(xì)菌覓食算法、遺傳算法。相比較,費(fèi)用比免疫克隆算法、蟻群算法、傳統(tǒng)細(xì)菌覓食算法、遺傳算法減小了5.781%,8.493%,10.6%,9.106%,收斂時(shí)長要比其他算法更短,對比免疫克隆算法、蟻群算法、傳統(tǒng)細(xì)菌覓食算法、遺傳算法,減小了5.815%,9.016%,14.058%,14.123%。