無(wú)線(xiàn)局域網(wǎng)的動(dòng)態(tài)切分與重構(gòu)

許士博　劉曉蘭　任豐原

(清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系　北京 100084)

(xshbo@csnet1.cs.tsinghua.edu.cn)

?

無(wú)線(xiàn)局域網(wǎng)的動(dòng)態(tài)切分與重構(gòu)

許士博劉曉蘭任豐原

(清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系北京 100084)

(xshbo@csnet1.cs.tsinghua.edu.cn)

Splitting and Restructuring a WLAN Dynamically

Xu Shibo, Liu Xiaolan, and Ren Fengyuan

(DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084)

AbstractDue to user mobility and favorite of collective activities, the distribution of users in WLANs is seriously uneven and changeable. When a lot of users congest in a WLAN, the WLAN performance degrades and the user experience becomes worse. To address dynamical congestion in a WLAN, existing solutions are unpractical. In this paper, through introducing shadow access point (SAP) and station mapping, a solution called splitting and restructuring dynamically (SRD) is proposed, and formal analysis of station mapping and performance is conducted, and an algorithm for the optimal mapping is devised. According to the change of WLAN status, SRD can dynamically split an overcrowded WLAN to multiple sub-WLANs and restructure them into a centralized WLAN. So, the distribution of stations in all sub-WLANs can be monitored and controlled centralizedly. SRD can reduce the number of stations in each sub-WLAN, and improve user throughput and alleviate the impact of both collisions and multi-rate. The simulation results show that SRD can improve the WLAN throughput a lot. Besides, SRD requires no modifications on user devices.

Key wordswireless local area network (WLAN); access point (AP); occasionally crowded; shadow AP (SAP); station mapping

摘要因用戶(hù)的游移和喜好集會(huì)活動(dòng)，用戶(hù)在無(wú)線(xiàn)局域網(wǎng)(wireless local area network, WLAN)中的分布是非常不均勻的且是動(dòng)態(tài)變化的.當(dāng)1個(gè)WLAN的用戶(hù)數(shù)量很大時(shí)，整個(gè)網(wǎng)絡(luò)和每個(gè)用戶(hù)的吞吐量都會(huì)大幅下降.對(duì)于1個(gè)WLAN范圍內(nèi)的間歇擁塞問(wèn)題，已有的性能改進(jìn)方法存在一些不足.因此，提出了1套WLAN動(dòng)態(tài)切分與重構(gòu)的方案SRD(splitting and restructuring dynamically)，引入了影子AP(shadow access point, SAP)和終端映射2個(gè)概念，并對(duì)終端映射和方案的整體性能進(jìn)行了形式化分析，設(shè)計(jì)了最優(yōu)映射的計(jì)算方法.該方案能根據(jù)網(wǎng)絡(luò)負(fù)載及狀態(tài)的變化，動(dòng)態(tài)地將1個(gè)擁擠的WLAN切分成若干子網(wǎng)，并重構(gòu)成1個(gè)微型的集中式架構(gòu)的WLAN，從而對(duì)各子網(wǎng)中的終端分布進(jìn)行監(jiān)控.因此，該方案能大幅減少1個(gè)子網(wǎng)中的終端數(shù)量，提高用戶(hù)吞吐量，緩解沖突和異構(gòu)速率的影響.仿真結(jié)果表明，該方案能成倍地提高網(wǎng)絡(luò)及每個(gè)用戶(hù)的吞吐量，此外，該方案的部署不需要用戶(hù)終端設(shè)備作任何的更改.

關(guān)鍵詞無(wú)線(xiàn)局域網(wǎng)；接入點(diǎn)；間歇擁塞；影子AP；終端映射

當(dāng)前，無(wú)線(xiàn)接入點(diǎn)(access point, AP)被廣泛地部署在很多公共場(chǎng)所，為了以最低的成本覆蓋最大的面積，AP的部署在地里位置上一般都是均勻分布的，尤其是那些由運(yùn)營(yíng)商、單位、學(xué)校、小區(qū)統(tǒng)一批量部署的AP.然而，用戶(hù)在無(wú)線(xiàn)局域網(wǎng)(wireless local area network, WLAN)中的分布是嚴(yán)重不平衡且動(dòng)態(tài)變化的.比如,在學(xué)校白天用戶(hù)大都集中在教室和圖書(shū)館，就餐時(shí)間則會(huì)轉(zhuǎn)移到食堂，而晚上又聚集到宿舍.1個(gè)更為具體的實(shí)例，在2008年ACM SIGCOMM大會(huì)上，WLAN活躍用戶(hù)的數(shù)量在5～90之間周期地波動(dòng)[1].在用戶(hù)比較擁擠的WLAN中，網(wǎng)絡(luò)和每個(gè)用戶(hù)的吞吐量都比較低,由于用戶(hù)不規(guī)則的游移，總有些AP會(huì)間歇(偶發(fā))地處于擁塞狀態(tài).本文的研究重點(diǎn)和目標(biāo)就是解決小范圍內(nèi)的間歇擁塞問(wèn)題，即當(dāng)1個(gè)WLAN范圍內(nèi)聚集很多用戶(hù)時(shí)，提升WLAN和每個(gè)用戶(hù)的吞吐量.

在用戶(hù)很多時(shí)吞吐量較差的主要原因有3個(gè)：1)每個(gè)用戶(hù)所能分得的傳輸機(jī)會(huì)減少；2)隨著用戶(hù)數(shù)量的增多，因同時(shí)發(fā)送引發(fā)的沖突增多，影響了網(wǎng)絡(luò)的性能；3)異構(gòu)速率(也稱(chēng)為性能異常(perfor-mance anomaly)[2])和異構(gòu)傳輸模式的影響，用戶(hù)越多設(shè)備的異構(gòu)性和傳輸距離的差異越大，異構(gòu)速率和異構(gòu)傳輸模式的影響也就越大，這進(jìn)一步降低了網(wǎng)絡(luò)性能.

學(xué)術(shù)界為解決以上問(wèn)題，已有很多的研究和成果.文獻(xiàn)[3-4]將移動(dòng)通信中的小區(qū)呼吸技術(shù)引入到WLAN中，可以動(dòng)態(tài)地減少1個(gè)WLAN中的用戶(hù)數(shù)，以提升每個(gè)用戶(hù)分得的帶寬.文獻(xiàn)[5-6]使用非分布式協(xié)調(diào)功能DCF(distributed coordination function)的方法來(lái)避免或減少?zèng)_突.文獻(xiàn)[7-10]分別使用了不同的方法來(lái)緩解異構(gòu)速率的影響.然而，以上所有方法與現(xiàn)有終端設(shè)備都是不兼容的，它們需要修改用戶(hù)的終端設(shè)備.由于終端設(shè)備大都屬于用戶(hù)個(gè)人所有，以上條件在現(xiàn)實(shí)中難以得到滿(mǎn)足.

在現(xiàn)實(shí)中，為緩解間歇擁塞帶來(lái)的壓力，可以臨時(shí)地部署一些普通AP或移動(dòng)AP(也稱(chēng)為便攜AP).但是，在大部分環(huán)境下，AP的連線(xiàn)很不方便.此外，因移動(dòng)AP的回程鏈路是移動(dòng)通信網(wǎng)絡(luò)，其帶寬容量有限且流量收費(fèi)，主要適用于個(gè)人.另一方面，即使臨時(shí)地部署了一些AP或移動(dòng)AP，用戶(hù)在各AP之間的恰當(dāng)分配也無(wú)法實(shí)現(xiàn)和保證.已證實(shí)，用戶(hù)在AP間的分配是1個(gè)影響WLAN性能的重要因素[3]，因?yàn)閃LAN的性能不僅與用戶(hù)的數(shù)量有關(guān)，還與各用戶(hù)傳輸?shù)膱?bào)文大小、傳輸速率高低等因素有關(guān).

為提升小范圍間歇擁塞情況下網(wǎng)絡(luò)及用戶(hù)的吞吐量，本文提出一套無(wú)線(xiàn)局域網(wǎng)動(dòng)態(tài)切分與重構(gòu)的方案SRD(splitting and restructuring dynamically).該方案的核心思想是將1個(gè)WLAN重構(gòu)成1個(gè)微型的集中式(centralized)架構(gòu)的WLAN，通過(guò)動(dòng)態(tài)地調(diào)整其拓?fù)浣Y(jié)構(gòu)來(lái)保持最優(yōu)的性能.因?yàn)楝F(xiàn)有的AP無(wú)法方便、有效地解決間歇擁塞問(wèn)題，為此，SRD引入了1種特殊的AP，即影子AP(shadow AP, SAP)，SAP能實(shí)現(xiàn)WLAN的切分，且使用高吞吐量的WLAN作為回程鏈路.同時(shí)，本文將用戶(hù)在AP之間的分配形式化為終端映射問(wèn)題，并對(duì)該問(wèn)題進(jìn)行了分析和求解，提出了1個(gè)啟發(fā)式算法.利用以上概念和方法，SRD能將1個(gè)WLAN動(dòng)態(tài)地切分為多個(gè)子網(wǎng)(sub-WLAN)，這樣可以實(shí)現(xiàn)：

1) 多個(gè)子網(wǎng)在多個(gè)信道上進(jìn)行并行傳輸，提升信道傳輸容量，減少1個(gè)子網(wǎng)中的用戶(hù)數(shù)量，減少?zèng)_突.

2) 通過(guò)動(dòng)態(tài)地、有策略地調(diào)整終端映射，能保證用戶(hù)在AP之間的最佳分配，緩解異構(gòu)速率和異構(gòu)傳輸模式的影響.

與已有的方法不同，SRD的部署很簡(jiǎn)便，不需在用戶(hù)終端設(shè)備上做任何改動(dòng).仿真結(jié)果表明，SRD不僅能提升WLAN的吞吐量，還能在一定程度上保證終端之間的公平.

1背景及相關(guān)工作

1.1背景

WLAN是基于IEEE 802.11[11]標(biāo)準(zhǔn)的，使用DCF工作模式.任何一個(gè)終端在發(fā)送數(shù)據(jù)前，必須先監(jiān)測(cè)信道，如果信道連續(xù)空閑時(shí)間達(dá)到了分布式幀間間隔(distributed inter frame space, DIFS)，該終端即進(jìn)行發(fā)送，否則它將啟動(dòng)1個(gè)由二進(jìn)制指數(shù)退避(binary exponential backoff, BEB)算法控制的計(jì)時(shí)器.當(dāng)該計(jì)時(shí)器達(dá)到零時(shí)，該終端將再次嘗試發(fā)送.如果只有1個(gè)終端在發(fā)送數(shù)據(jù)，該傳輸就能成功，否則就會(huì)發(fā)生沖突，傳輸失敗.可見(jiàn),沖突是1個(gè)影響WLAN性能的重要因素.

DCF是1個(gè)為所有終端提供均等傳輸機(jī)會(huì)的資源分配算法，它不考慮各終端在物理層實(shí)際的傳輸速率，也就是說(shuō)在一段時(shí)間內(nèi)所有終端傳輸?shù)膸瑪?shù)是均等的.所以，當(dāng)不同傳輸速率的終端共存時(shí)，高速終端與低速終端的吞吐量是相等的[2]，這就是異構(gòu)速率問(wèn)題.由于低速終端要花更長(zhǎng)的時(shí)間去傳輸1個(gè)幀，所以異構(gòu)速率將損害WLAN的性能[2].當(dāng)前，異構(gòu)速率的影響越來(lái)越明顯的2個(gè)原因是：1)隨著物理層傳輸速率的迅速提高，最低速率到最高速率之間的差距越來(lái)越大，在進(jìn)行數(shù)據(jù)傳輸時(shí)，通過(guò)速率自適應(yīng)，終端可以采用任一支持的速率進(jìn)行傳輸；2)從IEEE 802.11b到IEEE 802.11n，該標(biāo)準(zhǔn)系列都是向后兼容的，也就是說(shuō)最新的標(biāo)準(zhǔn)必須能夠識(shí)別早期的傳輸模式和傳輸速率.此外，向后兼容性還引發(fā)了另外一個(gè)問(wèn)題，即異構(gòu)傳輸模式.為了避免不兼容的傳輸模式之間的干擾，需要采用一些相應(yīng)的保護(hù)機(jī)制，比如RTSCTS(request to sendclear to send)和CTS-to-self，這些保護(hù)機(jī)制帶來(lái)一定的開(kāi)銷(xiāo)，也影響了WLAN的性能[12].

隨著終端數(shù)量的增多，DCF的固有特性導(dǎo)致了3個(gè)后果：1)較多的終端意味著每個(gè)終端所能得到的傳輸機(jī)會(huì)很少；2)較多的終端意味著較多的沖突，這進(jìn)一步減少了成功傳輸?shù)臋C(jī)會(huì)；3)較多的終端還導(dǎo)致了更嚴(yán)重的異構(gòu)速率和異構(gòu)傳輸模式的影響.所以，在用戶(hù)或終端比較擁擠的環(huán)境下，WLAN和用戶(hù)的吞吐量很低.

1.2相關(guān)工作

截止到目前，關(guān)于增加傳輸機(jī)會(huì)數(shù)量、減少?zèng)_突、緩解異構(gòu)速率和異構(gòu)傳輸模式影響的研究工作有很多，現(xiàn)簡(jiǎn)要綜述如下.

為了增加傳輸機(jī)會(huì)數(shù)量，文獻(xiàn)[3-4]將移動(dòng)通信中的小區(qū)呼吸技術(shù)引入到了WLAN中，它通過(guò)調(diào)整發(fā)送功率來(lái)調(diào)節(jié)AP的覆蓋范圍，從而改變網(wǎng)絡(luò)中的終端數(shù)量，減少網(wǎng)絡(luò)中的終端數(shù)就可以增多每個(gè)終端的傳輸機(jī)會(huì)，但該方法需要AP設(shè)備支持動(dòng)態(tài)的功率控制.自IEEE 802.11n開(kāi)始，幀聚合(frame aggregation)和塊確認(rèn)(block-ACK)技術(shù)被用來(lái)提升WLAN的MAC(media access control)效率[13].從另一個(gè)角度看，這2項(xiàng)技術(shù)也可以增多傳輸機(jī)會(huì)，如果在1次傳輸中，利用幀聚合傳輸x個(gè)幀，那么傳輸機(jī)會(huì)相當(dāng)于增多了x倍.關(guān)于幀聚合的研究也有不少，比如文獻(xiàn)[13-15]，在如何有效使用幀聚合方面，它們都有很好的參考價(jià)值.然而，一方面,由于等待和處理時(shí)延較大，幀聚合在現(xiàn)實(shí)中的應(yīng)用程度還不夠;另一方面,雖然1個(gè)聚合幀中允許有多個(gè)來(lái)自不同終端的子幀，但WLAN的拓?fù)浣Y(jié)構(gòu)使得這種幀轉(zhuǎn)發(fā)現(xiàn)象不會(huì)出現(xiàn).還有些研究試圖通過(guò)減少開(kāi)銷(xiāo)來(lái)增多傳輸機(jī)會(huì)，文獻(xiàn)[16]提出了一種基于散列(hashing)的退避和無(wú)競(jìng)爭(zhēng)的訪(fǎng)問(wèn)方法，文獻(xiàn)[17]則提出了1個(gè)混合的信道預(yù)留競(jìng)爭(zhēng)方法，雖然這些方法能有效地減少等待開(kāi)銷(xiāo)，但它們需要修改終端設(shè)備，不便于部署.

為了避免沖突，文獻(xiàn)[5-6,16]提出了一些非DCF的方法，但它們與廣泛使用的DCF不兼容.小區(qū)呼吸技術(shù)也可以用來(lái)緩解沖突，通過(guò)減少1個(gè)WLAN中的終端數(shù)量，就可以減少?zèng)_突.然而，以上方法不適用于現(xiàn)有的用戶(hù)終端設(shè)備.

因?yàn)閭鬏斁嚯x與傳輸速率之間有很強(qiáng)的相關(guān)性[9]，較遠(yuǎn)的距離意味著較低的傳輸速率.為了緩解異構(gòu)速率影響、提升較遠(yuǎn)終端的傳輸速率，文獻(xiàn)[9-10]提出了中繼的方法，中繼結(jié)點(diǎn)部署在AP與較遠(yuǎn)終端之間，這樣，從較遠(yuǎn)終端到中繼結(jié)點(diǎn)、從中繼結(jié)點(diǎn)到AP的傳輸速率就能得到提升(距離縮短了).經(jīng)過(guò)2跳高速鏈路傳輸1個(gè)幀的時(shí)間要小于經(jīng)過(guò)1跳低速鏈路的傳輸時(shí)間，這樣也就提高了傳輸性能.中繼方法能從一定程度上減緩異構(gòu)速率和異構(gòu)傳輸模式的影響，但它有2方面的缺陷：1)如果低速終端的傳輸速率已經(jīng)是它所能支持的最高速率了，中繼方法不僅不能帶來(lái)任何好處，還會(huì)增加開(kāi)銷(xiāo)；2)對(duì)于每個(gè)被中繼的幀來(lái)說(shuō)，要至少經(jīng)歷2次基于DCF的傳輸，所以中繼效率很低、開(kāi)銷(xiāo)很大.此外，為解決異構(gòu)速率影響，文獻(xiàn)[7-8]提出了傳輸時(shí)間公平(airtime fairness)的信道分配方法，但它們與現(xiàn)有標(biāo)準(zhǔn)不兼容.

此外，新發(fā)布的IEEE 802.11ac[18]不僅支持更高的傳輸速率，還能在5 GHz頻段上使用更多的非重疊信道.然而，越高的傳輸速率意味著越低的MAC效率[13]和越嚴(yán)重的異構(gòu)速率影響，所以，僅靠提高傳輸速率來(lái)提高性能其效果是有限的.

在現(xiàn)實(shí)中，為緩解間歇擁塞，部署一些臨時(shí)AP是1個(gè)簡(jiǎn)單直觀的方法.但是，一方面，靜態(tài)部署的成本很高，因?yàn)闊o(wú)法確定擁塞會(huì)在何時(shí)出現(xiàn)在何地，只能盡量多地部署一些冗余AP；另一方面，動(dòng)態(tài)部署又很不方便，主要是線(xiàn)纜連接困難.雖然移動(dòng)AP無(wú)需線(xiàn)纜，但它們的回程鏈路一般是移動(dòng)通信網(wǎng)絡(luò)，所以帶寬容量有限且流量是收費(fèi)的.更重要的是，無(wú)論部署以上哪種AP，都不能保證終端在AP之間的合理分配，這也很大程度地影響著WLAN的性能.

此外，成熟的mesh網(wǎng)絡(luò)雖然能解決無(wú)線(xiàn)接入問(wèn)題，比如IEEE 802.16j中的中繼機(jī)制，但它主要解決的是無(wú)限覆蓋、移動(dòng)、接入和組網(wǎng)問(wèn)題，有1套完整的管理機(jī)制和協(xié)議，適用于較大的地理范圍.一方面，現(xiàn)用的用戶(hù)設(shè)備大都不支持mesh，WLAN中也缺乏完整的管理機(jī)制和協(xié)議;另一方面，無(wú)線(xiàn)用戶(hù)往往聚集在1個(gè)較小的空間內(nèi)(如報(bào)告廳)，這是mesh無(wú)法解決的.對(duì)于大規(guī)模統(tǒng)一部署而言，集中式WLAN架構(gòu)，即“瘦AP+AC(access control)”，是最合適的選擇，它的主要優(yōu)點(diǎn)是方便的管理、監(jiān)控、收費(fèi)、移動(dòng)，在部署時(shí)瘦AP往往也是均勻部署的，希望以最低的成本覆蓋最大的面積.一方面，在集中式架構(gòu)中也存在小范圍內(nèi)的擁塞問(wèn)題，如1個(gè)瘦AP范圍內(nèi)擁擠過(guò)多的用戶(hù);另一方面，AC雖然具有一定的負(fù)載均衡能力，但它的控制粒度和反應(yīng)條件太粗放，不適用于小范圍內(nèi)的間歇擁塞.

2SRD方案

本節(jié)將從整體上介紹SRD方案，包括它的動(dòng)機(jī)、概述和實(shí)現(xiàn)上的相關(guān)問(wèn)題.

2.1動(dòng)機(jī)

擁塞時(shí)WLAN及用戶(hù)吞吐量很低主要是因?yàn)檫^(guò)多的終端數(shù)，因此很自然地，比較直觀的方法是減少1個(gè)WLAN中的終端數(shù)，一旦終端數(shù)減少，每個(gè)終端所能得到的傳輸機(jī)會(huì)就會(huì)增多，沖突數(shù)也減少了，異構(gòu)速率和異構(gòu)傳輸模式的影響也能得到緩解.

為了達(dá)到以上目的且不影響已有的用戶(hù)，要減少1個(gè)WLAN中的終端數(shù)只能是部署更多的AP，將1個(gè)WLAN切分成多個(gè)，然后將所有的用戶(hù)分?jǐn)偟蕉鄠€(gè)WLAN中.現(xiàn)實(shí)中部署臨時(shí)AP或移動(dòng)AP的方法遵循的就是這個(gè)道理，但它們面臨線(xiàn)纜連接或回程鏈路以及終端分配的問(wèn)題.當(dāng)前的技術(shù)發(fā)展，比如5 GHz、中繼以及幀聚合，使得WLAN切分更為可行.尤其是最新公布的IEEE 802.11ac，它工作在5 GHz頻段上，可同時(shí)使用的非重疊信道數(shù)量超過(guò)20個(gè)，而在傳統(tǒng)的2.4 GHz頻段上只有3個(gè)非重疊信道可用，因此將1個(gè)沖突域切分成多個(gè)是可能的.現(xiàn)在及以后主流的無(wú)線(xiàn)設(shè)備都支持IEEE 802.11ac，在不久的將來(lái)，5 GHz將成為WLAN的主要工作頻段，所以，WLAN的切分在現(xiàn)實(shí)中也是可行的，這樣可以實(shí)現(xiàn)多信道上的并行傳輸，能大幅提升WLAN的容量.另一方面，在應(yīng)用中繼技術(shù)時(shí)，中繼結(jié)點(diǎn)上往往會(huì)積累多個(gè)終端的很多幀，所以更便于使用幀聚合技術(shù)來(lái)進(jìn)一步優(yōu)化性能.

總之，以上各項(xiàng)技術(shù)的發(fā)展使得WLAN的動(dòng)態(tài)切分成為可能.

2.2概述

SRD是1個(gè)WLAN動(dòng)態(tài)重構(gòu)方案，通過(guò)引入影子AP和終端映射，基于已有的技術(shù)，SRD能動(dòng)態(tài)地將1個(gè)WLAN切分成多個(gè)子網(wǎng)，并有策略地將其重構(gòu)成1個(gè)微型的集中式架構(gòu)的WLAN，使網(wǎng)絡(luò)及每個(gè)用戶(hù)的吞吐量能得到倍增.

SRD的工作原理示意如圖1所示.在普通網(wǎng)絡(luò)模式下，9個(gè)終端連接到1個(gè)AP上，它們都工作在信道1上.使用SRD方案并引入2個(gè)SAP(SAP1和SAP2，無(wú)需支持多頻)，SAP1是1個(gè)獨(dú)立的物理實(shí)體，SAP2為1個(gè)普通的用戶(hù)終端(需要安裝額外的軟件).AP為每個(gè)SAP分配1個(gè)非重疊的信道(6和11)，并根據(jù)全網(wǎng)的終端信息有策略地把這些終端分配給SAP或自己，比如按距離就近分配.這樣，原有的1個(gè)WLAN就被切分為3個(gè)子網(wǎng)，它們分別工作在3個(gè)非重疊信道上(即信道1，6，11)，2個(gè)SAP像普通終端一樣通過(guò)信道1與AP通信.該重構(gòu)后的WLAN為1個(gè)微型的集中式架構(gòu)的WLAN，其中AP同時(shí)擔(dān)任著AC的角色.SAP1和SAP2也具有雙重角色：對(duì)于AP來(lái)講，它們是終端；而對(duì)于連接到它們的終端來(lái)講，它們又是AP.顯然，SRD具有4個(gè)優(yōu)點(diǎn)：

1) SRD將所有的終端分?jǐn)偟蕉鄠€(gè)子網(wǎng)中，很大程度地減少了1個(gè)子網(wǎng)中的終端數(shù)，每個(gè)終端所能得到的傳輸機(jī)會(huì)也就增多了，沖突數(shù)也就減少了；

2) SRD可以為每個(gè)子網(wǎng)分配1個(gè)獨(dú)立的、非重疊的信道，因此能夠?qū)崿F(xiàn)并行傳輸；

3) 通過(guò)將較遠(yuǎn)的低速終端連接到距離它們較近的SAP上，SRD能緩解異構(gòu)速率的影響；

4) 通過(guò)將相同傳輸模式的終端分配到1個(gè)子網(wǎng)中，SRD能減少異構(gòu)傳輸模式引發(fā)的開(kāi)銷(xiāo).

Fig. 1　Schematic diagram of SRD.圖1　SRD原理示意

SRD的工作流程如下：2個(gè)SAP在啟動(dòng)時(shí)掃描可用的AP和空閑信道，在用戶(hù)1或管理用戶(hù)指示下連入指定的AP或缺省AP(信道1).在SAP與AP之間可正常無(wú)線(xiàn)通信后，就開(kāi)始了SRD正常的工作流程，如圖2所示.首先，AP和SAP要實(shí)時(shí)收集網(wǎng)絡(luò)狀態(tài)信息，如各信道的可用狀態(tài)、各終端的流量和速率變化等，SAP需要將采集到的信息提交給AP.在初始時(shí)，AP要為各SAP分配非重疊的信道，若在運(yùn)行中信道的可用狀態(tài)發(fā)生了較大變化，還可為SAP重新分配信道.通過(guò)對(duì)采集到的網(wǎng)絡(luò)狀態(tài)信息進(jìn)行預(yù)處理，若發(fā)現(xiàn)變化程度超過(guò)一定閾值，AP則重新進(jìn)行映射計(jì)算.根據(jù)計(jì)算所得的最優(yōu)映射，若需要調(diào)整終端的分配，則AP將配合SAP控制終端進(jìn)行切換.若可用信道狀態(tài)發(fā)生了變化，AP還要配合SAP將某個(gè)子網(wǎng)遷移到另一個(gè)信道上.以上的循環(huán)過(guò)程雖然是持續(xù)進(jìn)行的，為減少開(kāi)銷(xiāo)，AP與SAP之間的交互、終端切換和信道切換的時(shí)機(jī)和次數(shù)需要進(jìn)行權(quán)衡.除了以上的管控流程，AP和SAP的另一個(gè)核心任務(wù)是協(xié)調(diào)完成流量的中繼和幀聚合.

Fig. 2　Workflow of SRD.圖2　SRD工作流程

在SRD方案中，存在2個(gè)關(guān)鍵問(wèn)題，即WLAN切分和終端分配.

1) WLAN的切分需要1個(gè)特殊的AP，其不需要任何線(xiàn)纜連接且具備高速、免費(fèi)的回程鏈路.因此，引入了SAP，SAP是1個(gè)與AP相似的網(wǎng)絡(luò)構(gòu)件，具有以下特點(diǎn)：

① SAP的回程鏈路是一條連接到普通AP的WLAN鏈路；

② SAP的服務(wù)集標(biāo)識(shí)(service set identifier, SSID)和與其相連的AP相同，所以SAP的存在對(duì)終端來(lái)講是透明的；

③ SAP集成了一些已有技術(shù)，如中繼、幀聚合和塊確認(rèn)，以最大程度地提高回程鏈路上的吞吐量；

④ SAP通過(guò)分時(shí)復(fù)用的方法，可以工作在多種模式(終端模式和AP模式)和多個(gè)信道上.

2) 如何將所有終端合理地分配到各個(gè)子網(wǎng)中.本文將終端分配定義為終端映射問(wèn)題，即終端與AP及SAP之間的對(duì)應(yīng)關(guān)系.不同的終端映射對(duì)應(yīng)著不同的終端分配，也影響著WLAN的性能.本文中，SRD期望的最優(yōu)終端映射(簡(jiǎn)稱(chēng)最優(yōu)映射)滿(mǎn)足3個(gè)條件：

① 最大化WLAN的吞吐量;

② 保持被中繼終端和未被中繼終端的公平性;

③ 保持實(shí)時(shí)性，即中繼流量的傳輸時(shí)間不超過(guò)指定閾值.

然而，尋找最優(yōu)映射是一個(gè)非常復(fù)雜的問(wèn)題，原因有2個(gè):1)可能的終端映射數(shù)量隨著終端數(shù)的增多成指數(shù)增長(zhǎng)即搜索空間太大;2)影響WLAN性能的因素有很多，包括終端數(shù)、幀長(zhǎng)分布、傳輸速率分布以及傳輸模式等.因此，要找到最優(yōu)映射，需要設(shè)計(jì)1種特殊的方法，相關(guān)的討論將在第3節(jié)進(jìn)行.

總之，通過(guò)引入SAP和終端映射，SRD利用已有的技術(shù)能動(dòng)態(tài)地對(duì)WLAN進(jìn)行切分和重構(gòu)，重構(gòu)后的WLAN因允許多信道并行傳輸、每個(gè)子網(wǎng)用戶(hù)數(shù)減少、沖突減少、異構(gòu)速率和異構(gòu)傳輸模式影響減小而吞吐量倍增.

2.3實(shí)現(xiàn)相關(guān)問(wèn)題

本節(jié)將討論SRD在技術(shù)上的可行性，包括終端的透明切換(handoff)、工作模式信道的快速切換(switch)和SAP的實(shí)現(xiàn)與部署問(wèn)題.

根據(jù)最優(yōu)映射計(jì)算結(jié)果，SRD需要通過(guò)控制終端切換來(lái)調(diào)整終端到AP或SAP的連接.為了不影響已有用戶(hù)的網(wǎng)絡(luò)連接，需要實(shí)現(xiàn)終端的透明切換.對(duì)該技術(shù)已有一些相關(guān)的研究，比如文獻(xiàn)[19]提出的虛擬AP技術(shù).由于重構(gòu)后的WLAN是1個(gè)微型的集中式架構(gòu)的WLAN，所有SAP和終端的配置信息(如IP地址)都存放在AP上，終端在不同SAP或AP之間的切換不會(huì)引起其IP地址的變化，所以，終端的正常通信不會(huì)因切換而中斷，即終端的切換對(duì)用戶(hù)來(lái)講是透明的.

在AP與被中繼終端之間中繼數(shù)據(jù)時(shí)，SAP需要交替地工作在終端模式和AP模式，且這2種模式通常工作在不同信道上，因此還需要同時(shí)進(jìn)行信道切換，為了減少工作模式和信道切換帶來(lái)的開(kāi)銷(xiāo)，必須采用快速切換技術(shù)，該技術(shù)的實(shí)現(xiàn)已經(jīng)比較成熟[20]，本文不再贅述.

在實(shí)現(xiàn)方式上，SAP可以是1個(gè)獨(dú)立的硬件，也可以是1個(gè)安裝在普通用戶(hù)終端上的軟件模塊.硬件方式的實(shí)現(xiàn)在部署時(shí)不需要用戶(hù)設(shè)備做任何改動(dòng)，但需要一些成本投資；軟件方式的實(shí)現(xiàn)需要在用戶(hù)設(shè)備上安裝軟件但不需要額外的投資.此外，本文只考慮SAP安裝了1個(gè)無(wú)線(xiàn)收發(fā)模塊，如果SAP安裝了多個(gè)無(wú)線(xiàn)收發(fā)模塊，那么它就可以在多個(gè)信道上同時(shí)進(jìn)行收發(fā)，也就不需要進(jìn)行工作模式和信道的切換了.此外，本文只考慮SAP以獨(dú)立物理硬件形態(tài)實(shí)現(xiàn).

很明顯，SAP的部署位置也是與性能相關(guān)的因素.此類(lèi)問(wèn)題，如中繼結(jié)點(diǎn)的安放，在文獻(xiàn)[9,21-23]中已進(jìn)行了廣泛深入的研究.在本文中，一方面，幾米的偏差對(duì)性能的影響不大，所以SAP的部署可憑經(jīng)驗(yàn)操作，比如用戶(hù)較為密集的、距離AP不太遠(yuǎn)(視線(xiàn)距離內(nèi))的位置.另一方面，SAP的安放是由最終使用者實(shí)施的，SRD的任務(wù)是在SAP的位置確定后對(duì)WLAN進(jìn)行合理的切分和重構(gòu).此外，因?yàn)镾AP和AP工作在非重疊信道上，所以，部署的SAP數(shù)量受所在場(chǎng)所的空閑信道數(shù)約束，也要考慮實(shí)際用戶(hù)數(shù)量的大小.

此外，由于AP掌握著整個(gè)WLAN的所有信息，也便于監(jiān)控網(wǎng)絡(luò)狀態(tài)的變化、計(jì)算最優(yōu)映射和調(diào)整終端分配，所以SRD在技術(shù)上是可行的.

3終端映射

本節(jié)描述SRD是如何解決2.2節(jié)所述的第2個(gè)關(guān)鍵問(wèn)題，即尋找最優(yōu)映射.首先，本節(jié)對(duì)終端映射進(jìn)行形式化分析，而后給出相應(yīng)的計(jì)算方法.

3.1形式化

假設(shè)1個(gè)靜態(tài)的(終端的數(shù)量與位置是固定的)WLAN由1個(gè)AP和n個(gè)終端組成，每個(gè)終端的物理層傳輸速率和幀大小都是固定的，所有終端都是飽和的，且所有的流量都是由終端發(fā)往AP的，以上假設(shè)與傳統(tǒng)的分析思路[24]一致.不妨將由n個(gè)終端組成的終端集合記為N={1,2,…,n}，幀長(zhǎng)集合記為S={s1,s2,…,sn}，傳輸速率集合記為R={r1,r2,…,rn}.由于異構(gòu)速率的影響與異構(gòu)傳輸模式的影響相似，為簡(jiǎn)化起見(jiàn)，將異構(gòu)傳輸模式的影響耦合到異構(gòu)速率中，即只考慮異構(gòu)速率的影響.

再假設(shè)有s個(gè)SAP部署在該WLAN中，每個(gè)都工作在獨(dú)立的非重疊信道上，任一終端到任一SAP的距離是固定的，因此可假設(shè)它們之間的傳輸速率也是固定的.設(shè)分配給任一SAPi的終端集合為Ni(Ni?N)，幀長(zhǎng)集合為Si(Si?S)，傳輸速率集合為Ri，分配給AP的終端(即未被中繼的終端)構(gòu)成集合N0.s+1個(gè)終端集合滿(mǎn)足2個(gè)條件：

N0∪N1∪N2∪…∪Ns=N，

?i,j,i≠j,0≤i≤s,0≤j≤s?Ni∩Nj=?.

定義1. 終端映射.1個(gè)終端映射就是1個(gè)可能的終端分配方案，形式化定義為

mk={{N0,S0,R0}k,{N1,S1,R1}k,…,{Ns,Ss,Rs}k}.

需要注意的是，同一終端到不同SAP的距離是不同的，所以該終端到不同SAP的傳輸速率也是不同的.因?yàn)榻K端總數(shù)為n，子網(wǎng)總數(shù)為s+1，所以共有(s+1)n個(gè)可能的終端映射.

因所有終端的幀長(zhǎng)都是固定的，為便于計(jì)算，將幀速率(單位時(shí)間內(nèi)成功傳輸?shù)膸瑪?shù))當(dāng)作吞吐量.對(duì)于1個(gè)普通WLAN{N,S,R}而言，其吞吐量記作F(N,S,R)，當(dāng)利用SRD方案和終端映射mk將其重構(gòu)后，其吞吐量記作FSRD(mk).

定義2. 最優(yōu)映射mo是1個(gè)特殊的終端映射，滿(mǎn)足條件：

?k,k≠o?FSRD(mo)≥FSRD(mk)，

FSRD(mo)>F(N,S,R).

也就是說(shuō)，基于最優(yōu)映射重構(gòu)后的WLAN能實(shí)現(xiàn)吞吐量的最大化.SRD方案的目標(biāo)就是尋找最優(yōu)映射，并基于最優(yōu)映射對(duì)WLAN進(jìn)行重構(gòu).3.2節(jié)將普通WLAN的吞吐量作為參考依據(jù)，通過(guò)比較來(lái)尋找最優(yōu)映射.

3.2普通WLAN的吞吐量

本節(jié)將推導(dǎo)普通WLAN的吞吐量.根據(jù)文獻(xiàn)[24]，1個(gè)WLAN的吞吐量為

F(N,S,R)=

(1)

其中，Ps是成功傳輸?shù)母怕?，Ptr是在任一時(shí)隙(slot time)中至少有1個(gè)幀在傳輸?shù)母怕剩琓slot是1個(gè)標(biāo)準(zhǔn)時(shí)隙的時(shí)間長(zhǎng)度.與文獻(xiàn)[24]相似但不同的是，在本文中，1個(gè)成功傳輸所占用信道的平均時(shí)間Ts是由n個(gè)終端的數(shù)值計(jì)算所得的均值.類(lèi)似地，1個(gè)沖突所占用信道的平均時(shí)間Tc也是由n個(gè)終端的數(shù)值計(jì)算所得的均值.

(2)

其中，TDIFS為分布式幀間間隔(DIFS),TSIFS為短幀間間隔(short inter frame space, SIFS),TPHY為數(shù)據(jù)幀和確認(rèn)(ACK)幀的物理層開(kāi)銷(xiāo)，對(duì)于1個(gè)固定的場(chǎng)景，這3個(gè)時(shí)間量都是固定的.在WLAN中，由于每個(gè)終端都享有均等的傳輸機(jī)會(huì)，因此1個(gè)成功傳輸所占用信道的平均時(shí)間為

Ts(N,S,R)=

(3)

當(dāng)發(fā)生沖突時(shí)，信道被占用的時(shí)間取決于耗時(shí)最長(zhǎng)的那個(gè)傳輸，即信道占用時(shí)間tc為

(4)

(5)

因此，終端i與1個(gè)或多個(gè)編號(hào)小于它的終端沖突的概率為

(6)

該沖突占用信道的時(shí)間為

(7)

所以，1次沖突占用信道的平均時(shí)間為

(8)

討論如何計(jì)算式(1)中的Ps和Ptr.假設(shè)條件沖突概率為p，即任一傳輸發(fā)生沖突的概率為p，那么很容易得到：

(9)

(10)

(11)

(12)

其中，W為最小競(jìng)爭(zhēng)窗口，m為最大退避次數(shù)，它們都是常量.因此，τ，Ptr，Ps都是n的函數(shù)，雖然很難得到它們的解析解，但可以計(jì)算出它們的數(shù)值解.

最后，沖突的平均信道占用時(shí)間Tc(N,S,R)和WLAN的吞吐量F(N,S,R)就能計(jì)算得出，因?yàn)樗薪K端的傳輸機(jī)會(huì)都是均等的，所以所有終端的吞吐量(幀速率)也是相等的，即任一終端的吞吐量為

(13)

3.3重構(gòu)后WLAN的吞吐量

對(duì)于1個(gè)給定的終端映射mk，計(jì)算基于它重構(gòu)的WLAN的吞吐量，首先計(jì)算任一子網(wǎng)的吞吐量.

為簡(jiǎn)化過(guò)程，忽略SAP工作模式切換和信道切換所帶來(lái)的開(kāi)銷(xiāo)，并且將完成1次收發(fā)的過(guò)程定義為1輪(round).也就是說(shuō)，在1輪中，SAP將從所有下屬的終端接收一定數(shù)量的幀，聚合后再轉(zhuǎn)發(fā)給AP，完成以上過(guò)程后該輪結(jié)束，新的1輪隨即開(kāi)始.對(duì)于任一SAPi，設(shè)其平均1輪的時(shí)間長(zhǎng)度為ti，工作在AP模式與終端模式的時(shí)間比例為αi.

當(dāng)SAPi工作在AP模式時(shí)，該子網(wǎng)(SWi)的吞吐量為F(Ni,Si,Ri)，可利用式(1)計(jì)算得出.當(dāng)SAPi工作在終端模式時(shí)，SWi的吞吐量為0.所以，在1輪中，SWi的平均吞吐量為

(14)

那么，SWi中每個(gè)終端的吞吐量為

(15)

要計(jì)算重構(gòu)后整個(gè)WLAN的吞吐量，需要知道AP下屬的終端數(shù)及它們的幀長(zhǎng)分布.連接在AP上的終端包括未被中繼的終端和s個(gè)SAP.下面討論由SAP發(fā)往AP的幀長(zhǎng)和AP下屬的活躍終端數(shù).

為了提高中繼效率和被中繼終端的競(jìng)爭(zhēng)力(相對(duì)于未被中繼終端)，SAP和AP之間的數(shù)據(jù)傳輸使用了幀聚合和塊確認(rèn)機(jī)制.幀聚合包括2種實(shí)現(xiàn)模式，即聚合MAC服務(wù)數(shù)據(jù)單元(aggregate MAC service data unit, AMSDU)和聚合MAC協(xié)議數(shù)據(jù)單元(aggregate MAC protocol data unit, AMPDU).前者有較高的聚合效率，但易受干擾影響，因此在現(xiàn)實(shí)中后者應(yīng)用的居多，在傳輸過(guò)程中，即使AMPDU中某些子幀發(fā)生錯(cuò)誤，其他子幀仍然可以使用，發(fā)生錯(cuò)誤的子幀還可以選擇性地進(jìn)行重傳.所以，本文也采用AMPDU模式進(jìn)行幀聚合，那么根據(jù)協(xié)議標(biāo)準(zhǔn)，有2個(gè)限制條件，即1個(gè)AMPDU中子幀的數(shù)量不能超過(guò)64，整個(gè)AMPDU幀的長(zhǎng)度應(yīng)小于64 KB(最大長(zhǎng)度為65 535 B).在現(xiàn)實(shí)網(wǎng)絡(luò)中，由于大部分報(bào)文的長(zhǎng)度都比較小，70%的報(bào)文長(zhǎng)度不到128 B[25]，所以，在下文分析中，為簡(jiǎn)單起見(jiàn)忽略幀長(zhǎng)限制.

對(duì)于SAPi，在1輪中，它有tiFi(Ni,Si,Ri)個(gè)幀需要聚合，因此，SAPi的1個(gè)AMPDU中的子幀數(shù)量為

(16)

由于SAPi下屬的終端發(fā)出的幀數(shù)在統(tǒng)計(jì)上是均等的，所以，1個(gè)AMPDU的平均長(zhǎng)度為

(17)

其中,ld為MPDU(MAC protocol data unit)定界符(delimiter)的長(zhǎng)度.

(18)

(19)

其中，rSAP,i表示SAPi與AP之間的傳輸速率，在一個(gè)固定的環(huán)境下，它是一個(gè)已知常量.

(20)

要求解基于終端映射mk重構(gòu)后的整個(gè)WLAN的吞吐量FSRD(mk)，還需要進(jìn)一步知道每個(gè)SAP在不同工作模式上的時(shí)間比例.根據(jù)以上分析，一旦ti和αi確定，F(xiàn)SRD(mk)就可計(jì)算得出，下面對(duì)此進(jìn)行討論.

為了保證實(shí)時(shí)性，中繼幀的傳輸必須在一定時(shí)間內(nèi)完成，設(shè)時(shí)間上限為tu，即中繼幀從被中繼終端到AP總的傳輸延時(shí)不超過(guò)tu.顯然，ti≤tu(1≤i≤s)，并且tu越大聚合的效率也就越高.因此，得到2個(gè)約束條件：

(21)

通過(guò)將約束條件(21)中的幀數(shù)最大化，可以得出ti，為了保證公平性，被中繼終端和未被中繼終端的吞吐量應(yīng)該相當(dāng)，即：

(22)

通過(guò)式(22)，可以計(jì)算出αi，也就保證了被中繼終端和未被中繼終端之間的公平性.式(22)給出了每個(gè)被中繼終端和未被中繼終端的吞吐量，所以，重構(gòu)后整個(gè)WLAN的吞吐量為

(23)

3.4最優(yōu)映射計(jì)算

根據(jù)3.3節(jié)的分析，對(duì)于任一給定的終端映射，可以計(jì)算出重構(gòu)后WLAN的吞吐量，因此，可以通過(guò)窮盡比較的方法找出最優(yōu)映射，過(guò)程如下：

1) 利用窮盡的方法找到每個(gè)可能的終端映射；

2) 計(jì)算基于每個(gè)終端映射重構(gòu)后的WLAN的吞吐量；

3) 通過(guò)比較所有終端映射對(duì)應(yīng)的WLAN的吞吐量，得出最優(yōu)映射.

利用以上方法尋找最優(yōu)映射需要完成2步操作：1)找到每種可能的終端映射，將n個(gè)終端分配到s+1個(gè)子網(wǎng)中，共有(s+1)n個(gè)可能的結(jié)果；2)計(jì)算每個(gè)終端映射對(duì)應(yīng)的WLAN的吞吐量，該過(guò)程包括一些復(fù)雜的數(shù)值計(jì)算.所以窮盡比較方法的復(fù)雜度是O((s+1)n)，主要由第1步?jīng)Q定.

由于以上方法過(guò)于復(fù)雜，需要找到1個(gè)更簡(jiǎn)單實(shí)用的方法.SRD方案的基本思路是動(dòng)態(tài)地對(duì)WLAN進(jìn)行切分，以允許多信道上的并行傳輸、減少1個(gè)子網(wǎng)中的終端數(shù).雖然不同的終端映射會(huì)對(duì)最終的性能有一些影響，在現(xiàn)實(shí)中，本文認(rèn)為1個(gè)次優(yōu)的終端映射也是可以接受的.由于影響WLAN性能的關(guān)鍵因素主要是終端數(shù)(與傳輸機(jī)會(huì)和沖突相關(guān))、傳輸速率和傳輸模式(與多速率相關(guān))，以及幀長(zhǎng)度(與MAC效率相關(guān))，因此，綜合考慮以上因素，本文提出1個(gè)啟發(fā)式算法如下：

1) 利用傳輸速率和幀長(zhǎng)度對(duì)終端集合S進(jìn)行排序.首先，用傳輸速率對(duì)S進(jìn)行遞增排序.如果有多個(gè)終端的傳輸速率相同，再按以下方法用幀長(zhǎng)度對(duì)這些終端進(jìn)行二次排序：如果傳輸速率等于最大的傳輸速率，則按幀長(zhǎng)度對(duì)這些終端進(jìn)行遞增排序，否則進(jìn)行遞減排序.

2) 如果|N0|>βmax{|N1|,|N2|,…,|Ns|}，則順序地從S中選取下一個(gè)終端i作為被中繼終端，否則算法結(jié)束.也就是說(shuō)，分配給每個(gè)SAP的最大終端數(shù)應(yīng)少于未被中繼的終端數(shù).其中，β(1.0≤β≤1.5)是1個(gè)調(diào)整被中繼終端和未被中繼終端比例的參數(shù).

3) 為終端i選擇1個(gè)合適的SAP(SAPj).不妨用r(x,y)表示x和y這2個(gè)結(jié)點(diǎn)之間的傳輸速率，SAPj需要滿(mǎn)足3個(gè)條件，依次用這3個(gè)條件對(duì)所有SAP進(jìn)行篩選，直到剩下1個(gè)SAP.條件1：SAPj是負(fù)載最輕的，即從其所有下屬終端各收1個(gè)幀所需時(shí)間之和最短;條件2：SAPj所帶來(lái)的時(shí)間增益(式(24))最大;條件3：分配給SAPj的終端數(shù)最少.

4) 將終端i分配給SAPj.

5) 返回步驟2)重復(fù)執(zhí)行，即繼續(xù)選擇下一個(gè)可被中繼的終端.

時(shí)間增益的計(jì)算方法為

(24)

該啟發(fā)式算法主要包含2步，即選擇可被中繼的終端和為終端選擇合適的SAP.由于所有終端的數(shù)據(jù)傳輸都要通過(guò)AP所在的信道，所以，提高該信道上的傳輸速率和MAC效率對(duì)所有終端都有好處，終端分配的1個(gè)重要原則就是最大程度地提高或保持該信道上的傳輸速率和MAC效率.由于不同終端使用信道的傳輸速率和MAC效率不同，所以該啟發(fā)式算法按一定順序來(lái)選擇可被中繼的終端.因?yàn)榈退俳K端的吞吐量低且影響所有其他終端的傳輸性能，所以低速終端優(yōu)先被選擇.對(duì)于多個(gè)傳輸速率相同的低速終端來(lái)講，幀長(zhǎng)越大的占用信道的時(shí)間越長(zhǎng)，所以?xún)?yōu)先選擇幀長(zhǎng)較大的；而對(duì)于高速終端而言，幀長(zhǎng)越小的MAC效率越低、吞吐量也就越低，因此優(yōu)先選擇幀長(zhǎng)較小的.此外，為了最大化WLAN的吞吐量，各子網(wǎng)之間應(yīng)盡量保持負(fù)載均衡，對(duì)于AP來(lái)講，低速終端因耗時(shí)更長(zhǎng)所以帶來(lái)的負(fù)載也就更大，因此，低速終端大都分配給了各SAP.又因?yàn)镾AP只是部分時(shí)間地工作在AP模式，所以，為各SAP分配的終端數(shù)應(yīng)少于未被中繼的終端數(shù).在該算法中，β就是1個(gè)調(diào)整被中繼終端和未被中繼終端數(shù)量的系數(shù).顯然，該算法的復(fù)雜度為O(ns)，它比窮盡比較算法更為簡(jiǎn)單.

以上討論和分析假設(shè)信道的帶寬是固定的，這也是當(dāng)前WLAN缺省的工作模式.為充分利用頻譜資源，一些新的研究提出了可變帶寬信道的思想，比如文獻(xiàn)[26]基于博弈理論研究了可變帶寬信道的分配策略.通過(guò)調(diào)整SRD方案中的相關(guān)參數(shù)，SRD也能適用于可變信道環(huán)境.

4驗(yàn)證

4.1實(shí)驗(yàn)驗(yàn)證

在如圖3所示的實(shí)驗(yàn)環(huán)境中，本節(jié)用以下設(shè)備驗(yàn)證了SAP的效果.

1) AP：Netgear WNDR3700；

2) 測(cè)試服務(wù)器：普通PC機(jī)，通過(guò)有線(xiàn)連接AP，用于接收并統(tǒng)計(jì)流量數(shù)據(jù)；

3) 終端1：聯(lián)想Thinkpad T430，距AP約7 m；

4) 終端2：PC機(jī)+360wifi2無(wú)線(xiàn)網(wǎng)卡，距AP約9 m；

5) 終端3：聯(lián)想Thinkpad X200，距AP約15 m；

6) 終端4：聯(lián)想Thinkpad X100，距AP約15 m；

7) 終端5：PC機(jī)+COMFASTCF-WU770N無(wú)線(xiàn)網(wǎng)卡，距AP約19 m；

8) SAP：PC機(jī)+360wifi2無(wú)線(xiàn)網(wǎng)卡+Netcore NW336無(wú)線(xiàn)網(wǎng)卡，距AP約8 m.

Fig. 3　Scenario of experiments.圖3　實(shí)驗(yàn)場(chǎng)景

本實(shí)驗(yàn)所用的SAP為一通用PC機(jī)，裝配了2個(gè)無(wú)線(xiàn)網(wǎng)卡：一個(gè)工作在普通網(wǎng)卡模式，用于向AP發(fā)送數(shù)據(jù)；另一個(gè)工作在AP模式，用于接收終端的數(shù)據(jù).在SAP上部署定制的轉(zhuǎn)發(fā)程序，在收到終端的數(shù)據(jù)包后，每累積12個(gè)數(shù)據(jù)包就合并為1個(gè)數(shù)據(jù)包，然后轉(zhuǎn)發(fā)給AP(模擬幀聚合).因使用了雙網(wǎng)卡，該SAP沒(méi)有模式切換開(kāi)銷(xiāo)，但中繼功能由上層應(yīng)用來(lái)完成，因此轉(zhuǎn)發(fā)效率略低.

首先5個(gè)終端通過(guò)無(wú)線(xiàn)關(guān)聯(lián)到AP(信道11)，然后向測(cè)試服務(wù)器循環(huán)發(fā)送UDP數(shù)據(jù)包，報(bào)文長(zhǎng)度均為100 B，在5 min內(nèi)測(cè)試服務(wù)器統(tǒng)計(jì)到的各終端吞吐量的累積分布函數(shù)(cumulative distribution function, CDF)如圖4所示.然后，終端3～5關(guān)聯(lián)到SAP(信道1)上， 以同樣的方式向測(cè)試服務(wù)器發(fā)送數(shù)據(jù)，統(tǒng)計(jì)到的各終端的吞吐量CDF如圖5所示，可知各終端有效的數(shù)據(jù)傳輸速率都有了明顯提升.2種環(huán)境下各終端5 min內(nèi)傳輸?shù)淖止?jié)數(shù)如圖6所示.5個(gè)終端總的吞吐量變化情況如圖7所示，可以看出，使用1個(gè)SAP后整個(gè)網(wǎng)絡(luò)及每個(gè)終端的吞吐量都有了明顯提升.由于實(shí)驗(yàn)室環(huán)境較復(fù)雜，周邊有10多個(gè)其他的AP，各設(shè)備形態(tài)性能不同，無(wú)線(xiàn)網(wǎng)卡的商家也不同，所以各終端所表現(xiàn)的傳輸性能也不同，傳輸速率也不穩(wěn)定.

Fig. 4　Distribution of station goodput without SAP.圖4　未使用SAP時(shí)各終端的吞吐量分布

Fig. 5　Distribution of station goodput with one SAP.圖5　使用1個(gè)SAP時(shí)各終端的吞吐量分布

Fig. 6　Received bytes by stations in five minutes.圖6　各終端5 min內(nèi)傳輸?shù)臄?shù)據(jù)量

Fig. 7　Total goodput of five stations.圖7　5個(gè)終端的聚合吞吐量

4.2仿真驗(yàn)證

Fig. 8　Scenario of simulation.圖8　仿真場(chǎng)景

本節(jié)通過(guò)仿真來(lái)驗(yàn)證SRD方案的性能和效果.在如圖8所示的仿真場(chǎng)景中有1個(gè)報(bào)告廳，1個(gè)AP部署在正前方，100個(gè)用戶(hù)在報(bào)告廳中通過(guò)WLAN訪(fǎng)問(wèn)互聯(lián)網(wǎng).這些用戶(hù)(終端)到AP的距離和傳輸速率分布如表1所示.其中，在距離AP較近的74個(gè)用戶(hù)中，4個(gè)用戶(hù)使用的是802.11g設(shè)備.所有終端的MSDU(MAC Service data unit)長(zhǎng)度隨機(jī)分布，構(gòu)成比例是70%為100 B，15%為1 024 B，15%為1 400 B[25].有3個(gè)SAP(SAP1，SAP2，SAP3)分別部署在3個(gè)不同的位置(A，B，C)，根據(jù)直觀經(jīng)驗(yàn)，3個(gè)SAP都部署在AP與較遠(yuǎn)用戶(hù)之間且用戶(hù)較多的位置，SAP之間保持一定的距離.802.11g終端的傳輸速率為54 Mbps，其他被中繼終端與SAP之間、SAP與AP之間的傳輸速率均為300 Mbps，其他MAC層的相關(guān)參數(shù)設(shè)置如表2所示.因?yàn)镾RD方案屬于MAC層的優(yōu)化方法，不考慮跨層因素的影響，所以，假設(shè)使用的所有信道都是理想的、非重疊的，對(duì)各網(wǎng)絡(luò)設(shè)備的物理特性也不做特殊要求，所有設(shè)備都能以預(yù)定的速率正常傳輸.

Table 1　Distance and Data Rate

因?yàn)榻?jīng)過(guò)中繼的幀要經(jīng)歷2次DCF競(jìng)爭(zhēng)，所以沖突對(duì)被中繼終端的影響要大于未被中繼終端.SAP和各未被中繼終端面臨相同的沖突概率，未被中繼終端遭遇沖突時(shí)僅丟失1幀，而SAP的AMPDU沖突時(shí)將丟失多個(gè)幀，所以，SAP的競(jìng)爭(zhēng)力應(yīng)進(jìn)一步提高，此類(lèi)方法有很多，在仿真中SAP的最小競(jìng)爭(zhēng)窗口為各終端的一半，終端數(shù)量比例系數(shù)β=1.2.

Fig. 9　Total frames sent and dropped.圖9　傳輸和丟棄的總幀數(shù)

比較4種不同場(chǎng)景下的WLAN性能：場(chǎng)景1為普通WLAN，即不使用任何SAP；場(chǎng)景2只使用一個(gè)SAP(SAP1)；場(chǎng)景3使用2個(gè)SAP(SAP1和SAP2)；場(chǎng)景4則使用3個(gè)SAP.比較30 s內(nèi)整個(gè)WLAN及每個(gè)終端的吞吐量，且每一實(shí)驗(yàn)重復(fù)10次取其均值作為統(tǒng)計(jì)結(jié)果.

圖9給出了不同場(chǎng)景下整個(gè)WLAN成功傳輸和丟棄的總幀數(shù)，橫坐標(biāo)表示不同場(chǎng)景對(duì)應(yīng)的SAP數(shù)，0對(duì)應(yīng)的為場(chǎng)景1，即沒(méi)有使用SAP.為了便于比較，把丟棄的幀數(shù)放大了50倍.由圖9可以看出，WLAN的吞吐量隨著SAP的增多而線(xiàn)性增長(zhǎng)，每增加1個(gè)SAP，吞吐量的增長(zhǎng)幅度約為初始(場(chǎng)景1)總量的70%;同時(shí)，因沖突而導(dǎo)致的丟包數(shù)也隨著SAP的增多而明顯減少，表明沖突概率隨著SAP的增多而大幅下降，如圖10所示:

Fig. 10　Collision rate declines as more SAPs are deployed.圖10　沖突概率隨著SAP的增多而下降

Fig. 11　Distribution of stations with different data rates in each sub-WLAN.圖11　各子網(wǎng)中不同速率終端的分布

下面，進(jìn)一步檢驗(yàn)不同速率和不同幀長(zhǎng)的終端在各子網(wǎng)中的分布.先按速率把所有終端分為3類(lèi)：高速(high rate)終端(300 Mbps)、中速(medium rate)終端(180 Mbps)和低速(low rate)終端(54～60 Mbps).同樣方式，按幀長(zhǎng)也把所有終端分為3類(lèi)：長(zhǎng)幀(large frame)終端(1400 B)、中幀(medium frame)終端(1024 B)和短幀(small frame)終端(100 B).圖11給出了不同速率的終端在各子網(wǎng)中的分布，SW0代表由未被中繼終端組成的子網(wǎng)，即AP所在的子網(wǎng)；SW1代表SAP1所在的子網(wǎng).圖12給出了不同幀長(zhǎng)的終端在各子網(wǎng)中的分布.這2個(gè)圖表明終端被分?jǐn)偟礁鱾€(gè)子網(wǎng)中，然而，終端的分配有以下2個(gè)明顯的特點(diǎn)：

1) 被中繼終端在各子網(wǎng)中的分布是比較均勻的.①各SAP下屬的被中繼終端的總量是相等或相近的；②各SAP的下屬終端中，不同速率、不同幀長(zhǎng)的終端分布也是均勻的.

Fig. 12　Distribution of stations with different frame sizes in each sub-WLAN.圖12　各子網(wǎng)中不同幀長(zhǎng)終端的分布

2) 被中繼終端和未被中繼終端之間的終端分布是不均勻的.例如，未被中繼終端的數(shù)量要大于任一子網(wǎng)中的被中繼終端的數(shù)量，不同速率、不同幀長(zhǎng)的終端在被中繼與未被中繼之間的分布也是不均勻的.

該現(xiàn)象的產(chǎn)生原因有3個(gè)：①為了充分提高AP(SW0)所在信道的吞吐量，低速終端和短幀終端大都被中繼了；②為了保持SAP之間的負(fù)載均衡，終端總數(shù)、不同速率或幀長(zhǎng)的終端數(shù)在各SAP之間的分配也是盡量均衡的；③為了保持被中繼終端的競(jìng)爭(zhēng)力，任一SAP下被中繼終端的數(shù)量少于未被中繼終端的數(shù)量.

Fig. 13　CDF of goodput variance of each station.圖13　各終端吞吐量方差的CDF

Fig. 14　Average frames sent by stations in each sub-WLAN.圖14　各子網(wǎng)中終端傳輸?shù)膸瑪?shù)均值

5總結(jié)

小范圍間歇擁塞情況下WLAN及用戶(hù)的吞吐量很低，為此，本文提出了1個(gè)SRD方案，通過(guò)引入影子AP和終端映射，SRD能對(duì)WLAN進(jìn)行動(dòng)態(tài)切分和合理重構(gòu).分析和仿真結(jié)果證明，SRD能很大程度地提升WLAN的吞吐量.此外，SRD的部署無(wú)需終端設(shè)備作任何改動(dòng).

參考文獻(xiàn)

[1]Gupta A, Min J, Rhee I. WiFox: Scaling WiFi performance for large audience environments[C]Proc of CoNEXT’12. New York： ACM, 2012: 217-228

[2]Heusse M, Rousseau F, Berger-Sabbatel G, et al. Performance anomaly of 802.11b[C]Proc of IEEE Int Conf on Computer Communications (IEEE INFOCOM’03). Piscataway, NJ: IEEE, 2003: 836-843

[3]Bahl P, Hajiaghayi M, Jain K, et al. Cell breathing in wireless LANs: Algorithms and evaluation[J]. IEEE Trans on Mobile Computing, 2007, 6(2): 164-178

[4]Bejerano Y, Han S. Cell breathing techniques for load balancing in wireless LANs[J]. IEEE Trans on Mobile Computing, 2009, 8(6): 735-749

[5]Kim S, Verma L, Choi S, et al. Collision-aware rate adaptation in multi-rate WLANs: Design and implementation[J]. Computer Networks, 2010, 54(17): 3011-3030

[6]Lin J, Chen C, Feng K. Adaptive reservation-assisted collision resolution protocol for wireless local area networks[C]Proc of WCNC’09. Piscataway, NJ: IEEE, 2009: 1-6

[7]Joshi T, Mukherjee A, Yoo Y, et al. Airtime fairness for IEEE 802.11 multirate networks[J]. IEEE Trans on Mobile Computing, 2009, 7(4): 513-527

[8]Zhang M, Chen S, Jian Y. MAC-layer time fairness across multiple wireless LANs[C]Proc of IEEE Int Conf on Computer Communications (IEEE INFOCOM’10). Piscataway, NJ: IEEE, 2010: 1-9

[9]So A, Liang B. Enhancing WLAN capacity by strategic placement of tetherless relay points[J]. IEEE Trans on Mobile Computing, 2007, 6(5): 522-535

[10]Bahl P, Chandra R, Lee P, et al. Opportunistic use of client repeaters to improve performance of WLANs[J]. IEEEACM Trans on Networking, 2009, 17(4): 1160-1171

[11]IEEE Computer Society. IEEE Std 802.11-2012, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[S]. Los Alamitos, CA: IEEE Computer Society, 2012

[12]AirMagnet. Impact of legacy devices on 802.11n networks[OL].[2015-03-15].http:www.nle.comliteratureAirmagnet_impact_of_legacy_devices_on_80211n.pdf

[13]Li T, Ni Q, Malone D, et al. Aggregation with fragment retransmission for very high-speed WLANs[J]. IEEEACM Trans on Networking, 2009, 17(2): 591-604

[14]Kolap J, Krishnan S, Shaha N. Frame aggregation mechanism for high-throughput 802.11n WLANs[J]. International Journal of Wireless & Mobile Networks, 2012, 4(3): 141-153

[15]Skordoulis D, Ni Q, Chen H, et al. IEEE 802.11n MAC frame aggregation mechanisms for next-generation high-throughput WLANs[J]. IEEE Wireless Communications, 2008, 15(1): 40-47

[16]Starzetz P, Heusse M, Rousseau F, et al. Hashing backoff: A collision-free wireless access method[C]Proc of the 8th Int IFIP-TC 6 Networking Conf. Berlin: Springer, 2009: 429-441

[17]Zhang R, Ruby R, Pan J, et al. A hybrid reservationcontention-based MAC for video streaming over wireless networks[J]. IEEE Journal on Selected Areas in Communications, 2010, 28(3): 389-398

[18]IEEE Computer Society. IEEE Std 802.11ac-2013, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, Amendment 4: Enhancements for Very High Throughput for Operation in Bands Below 6GHz[S]. Los Alamitos, CA: IEEE Computer Society, 2013

[19]Grunenberger Y, Rousseau F. Virtual access points for transparent mobility in wireless LANs[C]Proc of WCNC’10. Piscataway, NJ: IEEE, 2010: 1-6

[20]Kandula S, Lin K, Badirkhanli T, et al. FatVAP: Aggregating AP backhaul capacity to maximize throughput[C]Proc of NSDI’08. Berkeley, CA: USENIX Association, 2008: 89-104

[21]So A, Liang B. Efficient wireless extension point placement algorithm in urban rectilineal WLANs[J]. IEEE Trans on Vehicular Technology, 2008, 57(1): 532-547

[22]Islam M, Dziong Z, Sohraby K, et al. Capacity-optimal relay and base station placement in wireless networks[C]Proc of ICOIN’12. Piscataway, NJ: IEEE, 2012: 358-363

[23]Lin B, Ho P, Xie L, et al. Optimal relay station placement in broadband wireless access networks[J]. IEEE Trans on Mobile Computing, 2010, 9(2): 259-269

[24]Bianchi G. Performance analysis of the IEEE 802.11 distributed coordination function[J]. IEEE Journal on Selected Areas in Communications, 2000, 18(3): 535-547

[25]Huda T. Throughput enhancement of IEEE 802.11 WLAN for multimedia communications[C]Proc of AH-ICI’09. Piscataway, NJ: IEEE, 2009: 1-6

[26]Huang Tingpei, Chen Haiming, Zhang Zhaoliang, et al. Variable-width channel allocation based on game theory in 802.11 networks[J]. Journal of Computer Research and Development, 2013, 50(10): 2059-2069 (in Chinese)(黃庭培, 陳海明, 張招亮, 等. 802.11網(wǎng)絡(luò)中基于博弈理論的可變帶寬信道分配研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(10): 2059-2069)

Xu Shibo, born in 1975. PhD. His main research interests include WLAN, performance analysis and optimization.

Liu Xiaolan, born in 1975. PhD candidate. Her main research interests include WLAN, mobile network, performance analysis and optimization.

Ren Fengyuan, born in 1970. PhD. Professor and PhD supervisor. His main research interests include DCN, virtualization, wireless, performance evaluation (renfy@tsinghua.edu.cn).

中圖法分類(lèi)號(hào)TN925.93; TP393

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61225011)；國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目(2012CB315803)

收稿日期：2014-10-21；修回日期：2015-05-05

This work was supported by the National Natural Science Foundation of China (61225011) and the National Basic Research Program of China (973 Program) (2012CB315803).