葛坤玉，　汪　鵬,　魏振春,　衛(wèi)　星

(1.合肥工業(yè)大學(xué) 資產(chǎn)經(jīng)營有限公司，安徽 合肥　230009； 2.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥　230009)

?

基于改進(jìn)鄰居圖的WLAN快速切換機(jī)制研究

葛坤玉1，汪鵬2,魏振春2,衛(wèi)星2

(1.合肥工業(yè)大學(xué) 資產(chǎn)經(jīng)營有限公司，安徽 合肥230009； 2.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥230009)

摘要:典型的切換過程包括掃描、認(rèn)證和重關(guān)聯(lián)3個(gè)階段,其中掃描階段占切換時(shí)延的90%以上,因此解決切換時(shí)延問題主要是降低掃描階段的時(shí)延。文章對(duì)傳統(tǒng)鄰居圖切換機(jī)制進(jìn)行了介紹,提出了基于改進(jìn)鄰居圖的WLAN快速切換機(jī)制。該機(jī)制綜合考慮接入點(diǎn)(access point,AP)的信號(hào)強(qiáng)度、負(fù)載以及移動(dòng)站點(diǎn)(station,STA)的運(yùn)動(dòng)方向,計(jì)算出每個(gè)AP的權(quán)值,確定候選AP的優(yōu)先級(jí);根據(jù)優(yōu)先級(jí)STA依次選擇候選AP進(jìn)行認(rèn)證重關(guān)聯(lián),直至成功,從而減少掃描信道數(shù)量,達(dá)到降低掃描時(shí)延的目的。仿真結(jié)果表明，該切換機(jī)制有效降低了切換時(shí)延,減少了乒乓切換的發(fā)生,滿足實(shí)時(shí)性應(yīng)用的需求,實(shí)現(xiàn)了快速切換。

關(guān)鍵詞:鄰居圖;無線局域網(wǎng);切換時(shí)延;快速切換

無線局域網(wǎng)(wireless local area network, WLAN)對(duì)移動(dòng)性的支持并非最初IEEE 802.11的優(yōu)先考慮,因?yàn)閱蝹€(gè)接入點(diǎn)(access point, AP)的信號(hào)足夠覆蓋如辦公室、家這種小的區(qū)域。但WLAN因高速率、低成本和易布設(shè)等特點(diǎn)而得到廣泛應(yīng)用,使得越來越多的對(duì)實(shí)時(shí)性要求高的應(yīng)用(如VoIP、多媒體等)得到大力的發(fā)展。

由于單個(gè)AP的信號(hào)覆蓋范圍是有限的,一般為100～400 m,移動(dòng)站點(diǎn)(station, STA)從一個(gè)AP的信號(hào)覆蓋區(qū)域向另一個(gè)AP信號(hào)覆蓋區(qū)域移動(dòng)時(shí),STA接收到的信號(hào)強(qiáng)度會(huì)逐漸減小,直到最后斷開與所關(guān)聯(lián)AP的連接,然后與新的AP建立連接,這就是傳統(tǒng)的切換過程硬切換[1]機(jī)制(hard handoff mechanism, HHM)。但這種機(jī)制產(chǎn)生較高的切換時(shí)延和丟包率,難以滿足實(shí)時(shí)性業(yè)務(wù)的需求。

針對(duì)切換問題,本文提出基于改進(jìn)鄰居圖的WLAN快速切換機(jī)制(improved neighbor graph handoff mechanism, INGHM),該機(jī)制綜合考慮STA接收到的信號(hào)強(qiáng)度(received signal strength indication, RSSI)、STA移動(dòng)方向以及AP負(fù)載情況,從鄰居圖中選出最合適的候選AP作為切換對(duì)象,降低切換時(shí)延和丟包率,減少乒乓切換現(xiàn)象,滿足應(yīng)用需求。

1切換過程及相關(guān)工作

1.1　802.11切換過程

802.11切換過程如圖1所示,包括掃描、認(rèn)證和重關(guān)聯(lián)3個(gè)階段,其中掃描階段時(shí)延占總時(shí)延的90%以上[2-5],所以本文主要研究的是如何降低掃描階段的時(shí)延。

圖1　802.11切換過程

掃描有2種模式,被動(dòng)掃描和主動(dòng)掃描[6]。

被動(dòng)掃描模式如圖2所示,STA等待每個(gè)信道上的AP周期性發(fā)送的信標(biāo)幀,通常每個(gè)AP信標(biāo)幀的發(fā)送周期約為100 ms,STA必須對(duì)每個(gè)信道一個(gè)接一個(gè)地掃描,若有11個(gè)信道需要掃描,那么掃描的時(shí)間將長(zhǎng)達(dá)1 s,因此被動(dòng)掃描模式不適合應(yīng)用于實(shí)時(shí)性業(yè)務(wù)。

主動(dòng)掃描模式如圖3所示,STA主動(dòng)向每個(gè)信道廣播探尋請(qǐng)求幀,當(dāng)AP接收到探尋請(qǐng)求幀時(shí),會(huì)返回探尋響應(yīng)幀,STA因此會(huì)發(fā)現(xiàn)該條信道上存在AP。主動(dòng)掃描的時(shí)延可以表示為:

N×MinChannelTime≤Tscan≤

N×MaxChannelTime

(1)

其中,N為掃描信道的數(shù)量;MinChannelTime為信道一直空閑到該時(shí)間就停止掃描該信道,一般為6.5 ms;MaxChannelTime為信道掃描時(shí)間達(dá)到MinChannelTime該信道仍然繁忙,則繼續(xù)掃描直到MaxChannelTime才停止掃描該信道,一般為11 ms。

圖2　被動(dòng)掃描模式

圖3　主動(dòng)掃描模式

1.2　相關(guān)工作

由(1)式可知,降低掃描時(shí)延主要是減少掃描信道的數(shù)量N或者調(diào)整MinChannelTime和MaxChannelTime。

為了降低切換時(shí)延,保證實(shí)時(shí)性業(yè)務(wù)對(duì)時(shí)延的要求,很多學(xué)者提出了新的切換機(jī)制。鄰居圖算法[7-9],即STA根據(jù)獲取的鄰居圖中的AP信息,只掃描當(dāng)前關(guān)聯(lián)AP的鄰居AP所在的信道,減少掃描信道以及掃描AP的數(shù)量,從而降低了掃描時(shí)延;但鄰居圖算法未考慮網(wǎng)絡(luò)負(fù)載情況以及STA運(yùn)動(dòng)方向,會(huì)造成乒乓切換,降低切換效率。

SyncScan算法[10]主要針對(duì)減少被動(dòng)掃描時(shí)延,使所有的AP時(shí)鐘同步,相同信道的AP在同一時(shí)間同時(shí)廣播信標(biāo)幀;但該算法需要使所用AP和STA達(dá)到精確的時(shí)鐘同步,因此有較大的額外代價(jià)。MultiScan算法[11]主要利用多個(gè)無線接口,一個(gè)用于數(shù)據(jù)傳輸,其他的用于信道掃描和切換；但是該算法需要多個(gè)無線接口的額外代價(jià)。

2網(wǎng)絡(luò)模型

WLAN網(wǎng)絡(luò)模型如圖4所示,對(duì)網(wǎng)絡(luò)模型作如下假設(shè):

(1) STA只在指定的軌道上行駛,軌道存在直線區(qū)域、拐彎區(qū)域以及分岔路。

(2) AP分布在軌道旁,采用全向天線且信號(hào)覆蓋范圍半徑為R。為了增加網(wǎng)絡(luò)的覆蓋,在軌道的拐彎區(qū)域以及分岔路的分叉點(diǎn)一定會(huì)布設(shè)AP。假設(shè)軌道不存在無AP覆蓋的區(qū)域,不存在發(fā)生故障的AP。

(3) STA在運(yùn)動(dòng)過程中的移動(dòng)方向是已知的,用向量v表示。

(4) AP的位置是固定且已知的,保存于服務(wù)器的數(shù)據(jù)庫中。

圖4　WLAN網(wǎng)絡(luò)模型

3改進(jìn)鄰居圖的快速切換機(jī)制

3.1　鄰居圖的建立

定義1用戶負(fù)載閾值(user load threshold, ULT)即AP能關(guān)聯(lián)STA的最大數(shù)量。

定義2用戶負(fù)載(user load, UL)即AP當(dāng)前所關(guān)聯(lián)的STA的數(shù)量。

UL和ULT都保存于每個(gè)AP中。在建立鄰居圖的階段,每個(gè)AP向服務(wù)器上傳如圖5所示的消息。

圖5AP上傳消息格式

其中,AP ID為每個(gè)AP的編號(hào);SSID(service set identifier)為AP的服務(wù)集標(biāo)識(shí);Channel表示AP所在的信道。服務(wù)器保存有每個(gè)AP的位置信息,將位置信息以及每個(gè)AP上傳的消息綜合在一起,根據(jù)(2)式即可確定AP之間的邊的關(guān)系為:

(2)

其中,(x1,y1)和(x2,y2)為2個(gè)AP的位置坐標(biāo)。

鄰居圖的定義為:

(3)

其中,G為鄰居圖;V為一個(gè)AP,V中包含了每個(gè)AP的ID、SSID、Channel、位置信息、UL和ULT等信息;E為邊的集合,根據(jù)(2)式可以確定2個(gè)AP之間是否存在邊的關(guān)系;NC(APi)為與編號(hào)APi的AP存在邊的關(guān)系的所有AP的集合。

根據(jù)位置坐標(biāo)將圖4的網(wǎng)絡(luò)模型轉(zhuǎn)換為鄰居圖,如圖6所示。

圖6　鄰居圖

3.2　切換過程

UL和ULT都保存于每個(gè)AP中,初始UL為0,當(dāng)有STA與AP關(guān)聯(lián),則該AP的UL值自動(dòng)加1,當(dāng)有STA與AP斷開連接,則該AP的UL值自動(dòng)減1,并立即通知服務(wù)器更新UL值。

定義3信號(hào)強(qiáng)度閾值(signal strength threshold, SST)即STA與當(dāng)前關(guān)聯(lián)AP所接收到的信號(hào)強(qiáng)度RSSI所達(dá)到的切換條件。

當(dāng)STA檢測(cè)到與當(dāng)前AP的RSSI值降到閾值SST以下,即RSSI

啟動(dòng)掃描階段,按照分組的信道依次掃描,從而減少了掃描信道的數(shù)量,減少掃描時(shí)間。又由于每個(gè)信道內(nèi)的AP數(shù)量也可以通過鄰居圖確定,所以在掃描每個(gè)信道時(shí)掃描完指定數(shù)量的AP之后就可以直接跳到下一個(gè)信道繼續(xù)掃描,而不必等待MinChannelTime或者M(jìn)axChannelTime才退出該信道的掃描,從而減少每個(gè)信道的掃描時(shí)間。在掃描階段獲取每個(gè)鄰居AP的RSSI值RSSIAPi。

由于每個(gè)AP的位置已知,且通過向服務(wù)器發(fā)送請(qǐng)求獲取到了鄰居AP的信息,STA在運(yùn)動(dòng)過程中的移動(dòng)方向v也是已知的,所以可以得到STA移動(dòng)方向與當(dāng)前AP和候選AP連線的夾角θ為:

(4)

其中,(x1,y1)為當(dāng)前關(guān)聯(lián)AP的位置坐標(biāo);(x2,y2)為候選AP的位置坐標(biāo);n為從當(dāng)前AP到候選AP的向量。

掃描每個(gè)AP之后,計(jì)算其權(quán)值,可得:

(5)

其中,ULTAPi為APi的用戶負(fù)載閾值;ULAPi為APi的用戶負(fù)載;WAPi為APi的權(quán)值,是AP負(fù)載、STA接收AP信號(hào)強(qiáng)度以及STA運(yùn)動(dòng)方向的綜合權(quán)值,α、β、γ是這3個(gè)方面的比重(α+β+γ=1)，根據(jù)需要給出。

根據(jù)權(quán)值WAPi的大小將鄰居AP排序,即STA關(guān)聯(lián)的優(yōu)先級(jí)順序。STA首先與權(quán)值WAPi最大的AP進(jìn)行認(rèn)證、重關(guān)聯(lián),如果失敗,則繼續(xù)與下一個(gè)AP認(rèn)證、重關(guān)聯(lián),依次進(jìn)行,直到重關(guān)聯(lián)成功。

切換的過程描述如下:

(1)STA在行駛過程中不斷檢測(cè)與當(dāng)前關(guān)聯(lián)AP的RSSI值,如果低于閾值則觸發(fā)切換過程。

(2) 從服務(wù)器的鄰居圖中獲取當(dāng)前關(guān)聯(lián)AP的鄰居AP信息,如果沒有獲取到AP信息則啟動(dòng)全信道掃描過程,否則按照鄰居AP信道分組掃描相應(yīng)信道的AP。

(3) 獲取每個(gè)被掃描AP的RSSI,計(jì)算權(quán)值,并排序,得到AP優(yōu)先級(jí)序列。

(4) 根據(jù)優(yōu)先級(jí)序列,與AP逐個(gè)認(rèn)證和重關(guān)聯(lián),直到重關(guān)聯(lián)成功,則切換完成。

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

對(duì)基于改進(jìn)鄰居圖的WLAN快速切換機(jī)制(INGHM)與傳統(tǒng)的鄰居圖切換機(jī)制(neighborgraph,NG)的性能進(jìn)行仿真對(duì)比,通過對(duì)使用2種機(jī)制在不同鄰居數(shù)量和信道數(shù)量的條件下所造成的切換時(shí)延,以及對(duì)在仿真時(shí)間內(nèi)2種機(jī)制切換的次數(shù)進(jìn)行分析,來比較2種機(jī)制。使用Matlab實(shí)現(xiàn)仿真,仿真參數(shù)見表1所列。

表1　仿真參數(shù)

在仿真時(shí)間內(nèi)2種機(jī)制切換的次數(shù)比較如圖7所示。由于NG鄰居圖切換機(jī)制只考慮RSSI值的大小,未考慮AP負(fù)載情況以及STA的運(yùn)動(dòng)方向,因而容易發(fā)生乒乓切換,造成較多的切換次數(shù),影響系統(tǒng)的整體性能。

圖7　切換次數(shù)

在不同鄰居數(shù)量的條件下2種機(jī)制的切換時(shí)延比較如圖8所示,從圖中可以看出NG隨著鄰居個(gè)數(shù)的增加,切換時(shí)延基本呈線性增長(zhǎng)趨勢(shì),在鄰居個(gè)數(shù)為6時(shí)切換時(shí)延超過50 ms；而INGHM在鄰居個(gè)數(shù)達(dá)到8時(shí)切換時(shí)延依然在50 ms以內(nèi),滿足實(shí)時(shí)性業(yè)務(wù)的需求。

圖8　不同鄰居個(gè)數(shù)條件下的切換時(shí)延

在不同信道數(shù)量的條件下2種機(jī)制的切換時(shí)延比較如圖9所示,從圖中可以看出NG隨著信道數(shù)量的增加,切換時(shí)延增長(zhǎng)明顯,而INGHM增長(zhǎng)較為緩慢,且在信道數(shù)量為11時(shí)切換時(shí)延保持在50 ms以內(nèi),保證了通信的實(shí)時(shí)性要求。

圖9　不同信道數(shù)量條件下的切換時(shí)延

5結(jié)束語

本文通過對(duì)切換過程以及近幾年研究工作的描述,在建立的網(wǎng)絡(luò)模型上提出了基于改進(jìn)鄰居圖的WLAN快速切換機(jī)制,通過對(duì)AP信號(hào)強(qiáng)度、AP負(fù)載情況和STA運(yùn)動(dòng)方向3個(gè)方面的綜合考慮,根據(jù)權(quán)值的高低確定優(yōu)先級(jí),按照優(yōu)先級(jí)依次選擇候選AP進(jìn)行切換直到切換成功，減少了切換時(shí)延以及乒乓切換情況的發(fā)生。仿真實(shí)驗(yàn)結(jié)果表明該機(jī)制降低了時(shí)延,滿足了實(shí)時(shí)性應(yīng)用對(duì)時(shí)延的要求。

[參考文獻(xiàn)]

[1]Liu Xiaojuan, Zhang Yanpeng. A fast handoff algorithm with high reliability and efficiency for CBTC systems[C]//Proceedings of IEEE International Conference on Transportation and Mechanical & Electrical Engineering (TMEE), 2011:1461-1464.

[2]Saxenan N, Roy A. Novel framework for proactive handover with seamless multimedia over WLANs[J]. Communications, IET, 2011, 5(9):1204-1212.

[3]Wu T Y, Weng W F. Reducing handoff delay of wireless access in vehicular environments by artificial neural network-based geographical fingerprint[J]. Communications, IET, 2011, 5(4): 542-553.

[4]Yan Ye,Qian Yi, Hu R Q Y.A novel channel probing/scanning scheme for secure fast handoff in IEEE 802.11-based wireless networks[C]//Proceedings of IEEE Global Telecommunications Conference, 2011: 1-6.

[5]韓江洪,周浩,魏振春,等. 基于平滑選擇掃描與動(dòng)態(tài)緩存的WLAN快速切換機(jī)制研究[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2013,36(10):1199-1202,1241.

[6]Li Chungsheng, Tseng Yungchih, Chao Hanchieh. A neighbor caching mechanism for handoff in IEEE 802.11 wireless networks[C]//Proceedings of International Conference on Multimedia and Ubiquitous Engineering, 2007:48-53.

[7]Sarddar D,Jana T,Patra T,et al.Fast handoff mechanism in WLANs based on neighbor graph information[C]//Proceedings of international Conference on Parallel,Distributed and Grid Computing, 2010:334-338.

[8]Mishra A, Shin M, Arbaugh W A. Context caching using neighbor graphs for fast handoffs in a wireless network[C]//Proceedings of Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies,2004:54.

[9]Sangheon P, Hakyung J, Taekyoung K, et al. A selective neighbor caching scheme for fast handoff in IEEE 802.11 wireless networks[C]//Proceedings of IEEE International Conference on Communications,2005:3599-3603.

[10]Ramani I, Savage S. SyncScan: practical fast handoff for 802.11 infrastructure networks[C]//Proceedings of INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 2005:675-684.

[11]Vladimir B, Arunesh M, Suman B. Eliminating handoff latencies in 802.11 WLANs using multiple radios: applications, experience, and evaluation[C]//Proceedings of the Fifth ACM SIGCOMM Conference on Internet Measurement (IMC), 2005:27-32.

(責(zé)任編輯胡亞敏)

Fast handoff mechanism based on improved neighbor graph for IEEE 802.11 wireless networks

GE Kun-yu1, WANG Peng2,WEI Zhen-chun2,WEI Xing2

(1.Assets Management Company Limited, Hefei University of Technology, Hefei 230009, China; 2.School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

Abstract:The typical handoff process consists of three phases, namely scan, authentication and re-association. More than 90% of handoff delay is caused by scan phase, and therefore reducing the delay in scan phase is the key to solve the handoff problem. In this paper, the traditional neighbor graph handoff mechanism is introduced, and a fast handoff mechanism based on improved neighbor graph for wireless local area network(WLAN) is presented. In the mechanism, the signal strength of access points(AP), loading of access points and the movement direction of the mobile stations(STA) are considered comprehensively, the weight of every access point is calculated so as to determine the priority of the candidate access points. The mobile stations select the access point according to the priority to handoff until they succeed. The mechanism reduces the number of scanning channels, thus reducing the scanning delay. The simulation results show that the mechanism reduces the handoff delay and the occurrence of ping-pong handoff, meets the requirements of real-time applications and achieves the goal of fast handoff.

Key words:neighbor graph; wireless local area network(WLAN); handoff delay; fast handoff

中圖分類號(hào):TN926.3

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1003-5060(2015)03-0336-05

doi:10.3969/j.issn.1003-5060.2015.03.010

作者簡(jiǎn)介：葛坤玉(1961-),男，江蘇如東人，合肥工業(yè)大學(xué)工程師.

基金項(xiàng)目：國家自然科學(xué)基金面上資助項(xiàng)目(61370088);國家國際科技合作專項(xiàng)資助項(xiàng)目(2014DFB10060)和安徽省高等學(xué)校省級(jí)自然科學(xué)研究資助項(xiàng)目(KJ2012A224;KJ2013ZD09)

收稿日期：2014-02-11；修回日期：2014-04-14