一種基于模糊邏輯的自適應(yīng)信標(biāo)交換算法*

李玉龍， 戚云軍， 張衡陽

(空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，陜西 西安 710077)

一種基于模糊邏輯的自適應(yīng)信標(biāo)交換算法*

李玉龍， 戚云軍， 張衡陽

(空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，陜西 西安 710077)

針對移動無線傳感器網(wǎng)絡(luò)中貪婪地理路由協(xié)議采用固定信標(biāo)周期導(dǎo)致通信暫盲的問題，提出了一種基于模糊邏輯的自適應(yīng)信標(biāo)交換算法。該算法以節(jié)點(diǎn)移動速度、節(jié)點(diǎn)剩余能量和鄰居節(jié)點(diǎn)的數(shù)量作為評價(jià)因素，利用模糊邏輯控制機(jī)制確定自適應(yīng)的信標(biāo)周期，提高了鄰居表構(gòu)建與維護(hù)的準(zhǔn)確性與實(shí)時(shí)性，為貪婪地理轉(zhuǎn)發(fā)提供了可靠依據(jù)。仿真結(jié)果表明：該算法有效減少了通信暫盲現(xiàn)象，降低了控制開銷和平均端到端時(shí)延，提高了分組交付率，適用于對傳輸可靠性要求高的大規(guī)模移動無線傳感器網(wǎng)絡(luò)。

移動無線傳感器網(wǎng)絡(luò)；貪婪地理路由；鄰居節(jié)點(diǎn)表；信標(biāo)交換；模糊邏輯

0 引 言

在移動傳感器網(wǎng)絡(luò)中，構(gòu)建高效的路由算法一直是被廣泛關(guān)注的內(nèi)容。隨著定位技術(shù)的發(fā)展，貪婪地理路由協(xié)議成為了研究的熱點(diǎn)。但固定周期的信標(biāo)交換算法應(yīng)用于移動環(huán)境中會產(chǎn)生通信暫盲[1]的問題，嚴(yán)重影響數(shù)據(jù)傳輸?shù)目煽啃?。針對該問題，Chen Q等人[2]基于節(jié)點(diǎn)預(yù)測位置誤差提出了APU(adaptive position update)策略，但靜態(tài)的誤差值影響了APU策略的性能。Xiang X等人[3]提出了SOGR(self-adaptive on-demand geographic routing)協(xié)議，實(shí)現(xiàn)了控制分組與數(shù)據(jù)分組的平衡，但沒有考慮節(jié)點(diǎn)的移動性、能量和密度。Ernst R等人[4]根據(jù)鄰居節(jié)點(diǎn)間鏈路數(shù)量的改變提出了自適應(yīng)的HELLO機(jī)制，但用靜態(tài)的方式計(jì)算鏈路改變和周期時(shí)間。Hernandez Cons N等人[5]提出用節(jié)點(diǎn)鏈路的改變率來調(diào)整信標(biāo)發(fā)送的比率，而該機(jī)制中用大量的固定值和閾值計(jì)算鏈路改變率，不適用于動態(tài)地?zé)o線自組網(wǎng)。Heissenbuttel M等人[6]提出了兩種信標(biāo)交換算法：1)依據(jù)距離，與Huang C J等人[7]提出的策略有同樣的缺點(diǎn)就是用固定距離來計(jì)算信標(biāo)發(fā)送時(shí)刻；2)依據(jù)速度，節(jié)點(diǎn)移動速度快的比慢的發(fā)送信標(biāo)頻繁。

上述算法從不同程度上克服了固定周期信標(biāo)交換算法的缺點(diǎn)，但都沒有依據(jù)節(jié)點(diǎn)移動性、節(jié)點(diǎn)剩余能量和鄰居節(jié)點(diǎn)數(shù)量的改變自適應(yīng)地廣播信標(biāo)，然而，同時(shí)滿足多約束條件的決策又是一個(gè)NP-hard問題。因此，本文采用模糊邏輯根據(jù)不同的網(wǎng)絡(luò)環(huán)境確定自適應(yīng)的信標(biāo)周期，克服了上述研究中的缺點(diǎn)，建立了更加動態(tài)的信標(biāo)交換策略。

1 模糊邏輯建模

一個(gè)典型的模糊控制系統(tǒng)包括3個(gè)步驟：模糊化、模糊推理、解模糊化。將節(jié)點(diǎn)的移動速度、節(jié)點(diǎn)剩余能量和鄰居節(jié)點(diǎn)的數(shù)量作為模糊控制系統(tǒng)的輸入，信標(biāo)周期作為決策輸出，其模型如圖1所示。本文采用三角形、Z形和S形三種隸屬函數(shù)，如式(1)、式(2)、式(3)所示

圖1 模糊邏輯控制機(jī)制

(1)

(2)

(3)

1.1 輸入變量的模糊器

對于節(jié)點(diǎn)移動速度V(Velocity)，定義了三個(gè)隸屬度函數(shù)。有三個(gè)模糊集分別為S(Slow),M(Medium),F(Fast)，分別表示節(jié)點(diǎn)移動速度為慢、中和快，其論域?yàn)閇0，6]，最小移動速度為0，最大移動速度為6 m/s。

對于鄰居節(jié)點(diǎn)的數(shù)量N(Number)，定義了三個(gè)隸屬度函數(shù)。有三個(gè)模糊集分別為S(Small),M(Medium),B(Big)，分別表示鄰居節(jié)點(diǎn)的數(shù)量為小、中等和大，其論域?yàn)閇0，30]，最小鄰居點(diǎn)的個(gè)數(shù)為0，最大為30。

對于節(jié)點(diǎn)剩余能量E(Energy)，定義了三個(gè)隸屬度函數(shù)。有三個(gè)模糊集分別為L(Low),M(Medium),H(High)，分別表示節(jié)點(diǎn)的剩余能量為低、中和高，其論域?yàn)閇0，30]，最低剩余能量為0，最高能量為30 kJ。

輸入變量的模糊集合如表1所示，其模糊隸屬度函數(shù)如圖2所示。

表1 輸入變量模糊集

圖2 輸入變量的模糊隸屬度函數(shù)

1.2 輸出變量的模糊器

對于信標(biāo)周期T(Time)，定義了五個(gè)隸屬度函數(shù)。如表2所示，有五個(gè)模糊集分別為VS(Very short),S(Short),M(Medium),L(Long),VL(Very long)，分別表示信標(biāo)發(fā)送周期很短、短、中等、長和很長，其論語為[0，6]，最大周期時(shí)間為6 s，圖3表示節(jié)點(diǎn)信標(biāo)周期的模糊隸屬度函數(shù)。

表2 信標(biāo)周期模糊集

圖3 信標(biāo)周期的模糊隸屬度函數(shù)

1.3 模糊推理與解模糊化

通過IF-THEN規(guī)則，以節(jié)點(diǎn)移動速度、鄰居節(jié)點(diǎn)數(shù)量和節(jié)點(diǎn)剩余能量的模糊隸屬度作為前件，可以推出后件信標(biāo)周期的模糊隸屬度，規(guī)則見表3。本文解模糊化應(yīng)用最大隸屬度法。

表3 信標(biāo)周期的模糊規(guī)則

2 仿真與分析

2.1 仿真模型與評價(jià)指標(biāo)

本文把基于模糊邏輯的自適應(yīng)信標(biāo)交換算法的路由協(xié)議稱為GPSR-FLAB，并與GPSR協(xié)議在相同的運(yùn)動場景下進(jìn)行比較。采用隨機(jī)路點(diǎn)模型，評價(jià)參數(shù)包括以下4個(gè)：1)即時(shí)吞吐量，單位時(shí)間內(nèi)Sink節(jié)點(diǎn)收到的數(shù)據(jù)量；2)分組交付率，Sink節(jié)點(diǎn)收到數(shù)據(jù)包與發(fā)送數(shù)據(jù)包的比率；3)控制開銷，信標(biāo)包與信標(biāo)包和成功發(fā)送的數(shù)據(jù)包總量之比；4)平均端到端時(shí)延，數(shù)據(jù)包發(fā)送到接收的時(shí)間間隔。仿真平臺使用NS2.30，場景如表4所示。

表4 仿真場景參數(shù)

2.2 仿真結(jié)果分析

由圖4可以直觀地看出：采用周期性信標(biāo)交換算法的GPSR(Periodic Beacon=3 s)協(xié)議存在通信暫盲現(xiàn)象，出現(xiàn)了大量數(shù)據(jù)包的丟失，并且隨著節(jié)點(diǎn)移動速率的增大變得更為嚴(yán)重，而采用自適應(yīng)信標(biāo)交換算法的GPSR-FLAB協(xié)議基本消除了通信暫盲現(xiàn)象，且受節(jié)點(diǎn)動態(tài)性的影響不大。

圖4 GPSR和GPSR-FLAB的即時(shí)吞吐量(Nodes=20)

圖5～圖7為GPSR協(xié)議和GPSR-FLAB協(xié)議在不同的網(wǎng)絡(luò)規(guī)模和不同的節(jié)點(diǎn)運(yùn)動速率情況下的分組交付率、控制開銷和平均端到端時(shí)延仿真結(jié)果。

圖5 分組交付率

如圖5(a)所示，隨著節(jié)點(diǎn)移動速率的增大，GPSR協(xié)議數(shù)據(jù)分組交付率降低，這是因?yàn)殡S著節(jié)點(diǎn)的高速移動，鄰居表很難準(zhǔn)確反映當(dāng)前時(shí)刻鄰居節(jié)點(diǎn)的位置信息，鄰居表記錄的最優(yōu)下一跳節(jié)點(diǎn)可能已經(jīng)移出發(fā)送節(jié)點(diǎn)的通信范圍，導(dǎo)致數(shù)據(jù)包的丟失。相比之下，GPSR-FLAB協(xié)議由于采用自適應(yīng)的信標(biāo)周期，能夠?qū)崟r(shí)準(zhǔn)確地維護(hù)鄰居信息表，為下一跳的選擇提供可靠依據(jù)，使得分組交付率一直保持較高水平，受網(wǎng)絡(luò)節(jié)點(diǎn)的運(yùn)動劇烈程度影響不大，對網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化具有很好的適應(yīng)性。圖5(b)說明在相同的運(yùn)動模型(v∈[1,3]m/s)、相同的節(jié)點(diǎn)通信范圍(100 m)下，采用固定周期性信標(biāo)交換的GPSR協(xié)議數(shù)據(jù)分組傳送成功率隨著網(wǎng)絡(luò)規(guī)模的增大而迅速降低，而GPSR-FLAB協(xié)議能保持較高的數(shù)據(jù)分組傳送成功率。

如圖6(a)所示，GPSR協(xié)議隨著節(jié)點(diǎn)運(yùn)動速率的增大，數(shù)據(jù)分組成功傳送的總數(shù)減少，而信標(biāo)分組數(shù)量基本保持不變，導(dǎo)致控制開銷增加，并隨著節(jié)點(diǎn)的運(yùn)動劇烈程度越大，控制開銷增加的幅度也越來越大。在GPSR-FLAB協(xié)議中信標(biāo)周期隨著節(jié)點(diǎn)運(yùn)動速率的增大而自適應(yīng)的減小，產(chǎn)生的信標(biāo)分組有所增加，導(dǎo)致控制開銷也有所增加，但是,GPSR-FLAB協(xié)議一直保持較高的分組交付率，使得控制開銷要明顯低于GPSR協(xié)議。圖6(b)說明隨著網(wǎng)絡(luò)規(guī)模的增大，數(shù)據(jù)傳送成功率的降低，控制開銷也逐漸增大，但GPSR-FLAB協(xié)議在控制開銷方面的優(yōu)勢更為明顯。

圖6 控制開銷

如圖7(a)所示，GPSP協(xié)議隨著網(wǎng)絡(luò)中節(jié)點(diǎn)運(yùn)動速率的增大，平均端到端時(shí)延大幅度增加。這是因?yàn)檗D(zhuǎn)發(fā)節(jié)點(diǎn)總是選擇歐氏距離離目的節(jié)點(diǎn)最近的鄰居節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，這樣的鄰居節(jié)點(diǎn)處在轉(zhuǎn)發(fā)節(jié)點(diǎn)通信邊界的概率較大，當(dāng)節(jié)點(diǎn)在高速移動或信標(biāo)周期比較長的情況下，在節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)之前就可能已經(jīng)移出了通信范圍，多次下一跳鄰居節(jié)點(diǎn)的不可達(dá)就造成了平均端到端時(shí)延的增加。GPSR-FLAB協(xié)議根據(jù)節(jié)點(diǎn)移動速率自適應(yīng)的調(diào)整信標(biāo)周期，維護(hù)了較準(zhǔn)確的鄰居表，為下一跳選擇提供了可靠依據(jù)，在平均端到端時(shí)延方面有較大的改善。圖7(b)說明隨著網(wǎng)絡(luò)規(guī)模的增大，導(dǎo)致平均端到端時(shí)延也隨之增加。

圖7 平均端到端時(shí)延

3 結(jié)束語

在貪婪地理路由協(xié)議中，廣泛使用的周期性信標(biāo)交換算法在拓?fù)渥兓囊苿訄鼍爸袝硗ㄐ艜好がF(xiàn)象，節(jié)點(diǎn)非最優(yōu)問題和控制開銷效能低的問題，對網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性和可靠性帶來了很大的影響。針對該問題，本文提出了一種基于模糊邏輯的自適應(yīng)信標(biāo)交換算法。仿真結(jié)果表明：該算法極大地減少或消除了通信暫盲現(xiàn)象，提高了數(shù)據(jù)傳輸?shù)目煽啃裕瑫r(shí)降低了控制開銷和平均端到端時(shí)延，節(jié)省了能量的消耗，延長了網(wǎng)絡(luò)壽命，因此，適合規(guī)模較大的移動無線傳感器網(wǎng)絡(luò)。

[1] 張衡陽,李瑩瑩,劉云輝.移動傳感器網(wǎng)絡(luò)自適應(yīng)信標(biāo)交換算法[J].軟件學(xué)報(bào),2008,19(11):3033-3041.

[2] Chen Q,Kanhere S S,Hassan M.Adaptive position update for geographic routing in mobile Ad Hoc networks[J].IEEE Trans Mob Comput,2013,12(3):489-501.

[3] Xiang X,Wang X,Zhou Z.Self-adaptive on-demand geographic routing for mobile Ad Hoc networks[J].IEEE Trans Mob Comput,2012,11(9):1572-1586.

[4] Ernst R,Martini P.Adaptive HELLO for the neighborhood disco-very protocol[C]∥Proc of the 37th IEEE Conference on Local Computer Networks(LCN),Florida，USA,2012:470-478.

[5] Hernandez-Cons N,Kasahara S,Takahashi Y.Dynamic Hello/Timeout timer adjustment in routing protocols for reducing overhead in MANETs[J].Comput Commun,2010,33(15):1864-1878.

[6] Heissenbuttel M,Braun T.Optimizing neighbor table accuracy of position-based routing algorithms[C]∥24th Annual Joint Conference of the IEEE Computer and Communications Societies,Piscataway,NJ,2005:1-13.

[7] Huang C J,Lai W K,Chuang Y T,et al.A dynamic alternate path QoS enabled routing scheme in mobile Ad Hoc networks[J].Wirel Inf Netws,2007,14(1):1-16.

[8] Raed Alsaqour,Maha Abdeihhaq.Effect of mobility parameters on the inaccuracy of the position information of position-based MANET routing[J].Wireless and Mobile Computer,2014,1(7):68-78.

[9] Gomes R Lopes,Junior W Moreira,Cerqueira E.Using fuzzy link cost and dynamic choice of link quality metrics to achieve QoS and QoE in wireless mesh networks[J].Netw Comput Appl,2011,34(2):506-516.

[10] 劉金琨.智能控制[M].北京:電子工業(yè)出版社,2007:18-30.

An adaptive beacon exchange algorithm based on fuzzy logic*

LI Yu-long, QI Yun-jun, ZHANG Heng-yang

(School of Information and Navigation, Air Force Engineering University, Xi’an 710077, China)

Aiming at problem that temporary communication blindness caused by greedy geographical routing protocol adopts stationary beacon exchange in mobile wireless sensor networks(WSNs), a novel adaptive beacon exchange algorithm is proposed.The algorithm adopts node moving speed, node residual energy, number of neighboring nodes as evaluation factors and confirm adaptive beacon period using fuzzy logic control mechanism.The adaptive beacon exchange algorithm can increase accuracy and realtime of neighbors table construction and maintenance and provide reliable basis for greedy geographical relay.Simulation shows that the proposed algorithm reduce phenomenon of temporary communication blindness,increases packet delivery ratio and reduce average end-to-end delay as well as control overhead, so it is suitable for application of large-scale mobile WSNs,which has high requirement for transmission reliability.

mobile wireless sensor networks; greedy geographical routing; neighbor node table; beacon exchange; fuzzy logic

2015—01—23

國家自然科學(xué)基金資助項(xiàng)目(61202490)；航空科學(xué)基金資助項(xiàng)目(2013ZC15008)

10.13873/J.1000—9787(2015)04—0144—04

TP 393

A

1000—9787(2015)04—0144—04

李玉龍(1990-)，男，甘肅蘭州人，碩士研究生，主要研究方向?yàn)闊o線自組網(wǎng)。