1 引言
近年來，隨著無線通信技術和城市公共交通事業的不斷發展，乘坐公車的乘客接入互聯網將極大的便利人們的生活。由于Wi-Fi技術能夠提供高帶寬、低代價的Internet接入特性，其越來越成為車載網絡通信的主要網絡技術手段。通過該技術，公車可以通過與在公車線路上的站點處安放的接入點AP通信來進行Internet訪問。

圖1 公車網絡系統架構
本文所研究的一種無線公車網絡結構——BusNet如圖1所示。該結構中，AP被安置于每個公車站點。AP的數量由該站點的公車數決定。如果為多AP情況（各個AP的通信能力相同），可指定一個AP為主通信AP。為了避免干擾，各個相鄰AP的使用信道不同（IEEE 802.11p標準可支持6個服務信道1個控制信道；IEEE 802.11g標準采用11個信道）。在熱點區域（例如火車站等），公車流量較大，可能設置多個AP供公車通信。AP與交換中心（SWitching Centre, SWC）連接。而所有的SWC由公車網絡控制中心（Public Bus Network Controller, PBNC）控制。SWC控制連接于它的各個AP之間的通信。SWC與PBNC連接，后者是一個公車網絡服務器，其中存放著各條線路的公車路徑信息、每個站點位置信息、站點處相關AP信息（AP標識號，AP數量，使用信道號，MAC地址等）以及公車歷史訪問信息（某一時段公車訪問某個AP的歷史接入時間等）。

圖2 公車首次接入網絡流程
公車首次接入網絡的過程如圖2所示。公車在初始運行時，首先在初始站點向AP發送其自己的線路號，并由AP進而轉發給SWC，SWC再向PBNC發送首次接入請求信息——L-Request，然后，PBNC查詢本地信息，并向該SWC發送接入回答信息——L-Answer，其中包含該公車被分配的IP地址，并將該地址和公車線路信息以及該公車沿途的AP相關信息。由于AP覆蓋范圍較小，當公車從一個站點即將運動到另一個站點之時，需要與一個站點的AP進行連接以便于網絡通信，此時就面臨切換的問題。該切換問題可能分為兩種情況，一種是單AP切換，即下一站點只有一個AP的情況；另一種是多AP切換，即下一站點放置了多個AP的情況。
目前關于此兩種切換問題已經出現了很多切換策略。由于傳統無線網絡中，切換的主要開銷在于信道掃描，針對單AP切換，越來越多的切換策略被提出以減少信道掃描時間（一般情況下，350～500ms）[1][2][3][4]。他們的主要工作在于選擇性地進行信道掃描和調整掃描參數兩方面。即便如此，以上工作也不完全適于公車網絡，因為其沒有利用公車的可預測移動特性來進行輔助切換方面的工作。另一方面，多AP切換的工作相對復雜得多。該問題又可細分為多AP的單AP接入以及多AP接入兩種解決方案。所以其實質上是一個AP選擇問題。目前，AP負載均衡是多AP切換的必須考慮的一個基本問題。在很多相關研究中都有涉及到[5][6][7]。在單AP接入的解決策略中，IEEE 802.11a/b/g協議采用信噪比優先的選擇方式。這種方法過于簡單，并沒有考慮AP負載均衡和系統吞吐率所受的影響等問題。Fahd[8]和Balachandran[9]提出考慮信噪比結合各AP負載均衡的AP接入算法，但這兩種算法會使系統吞吐率較低。在多AP接入的算法中，Aruna Balasubramanian等人提出了全連接的VI-FI策略[10]，成功提高了客戶的在線時間和傳輸成功率，但是其是以犧牲信道資源利用率為代價的，其所有客戶均使用同一信道。綜上，現有的切換方法均不適合公車網絡，因此結合公車網絡的特點提出一個適合公車通信的切換策略是十分必要的。本文利用公車的可預測移動性首先對單AP切換問題進行研究，提出了一種單AP切換策略——S-Handoff，該策略無需信道掃描，可大大減少切換開銷。另外，針對多AP切換提出了一種單AP接入的切換策略——M-Handoff。該策略在保證系統吞吐率的情況下提供了簡單而有效的AP負載均衡的AP選擇策略——BWT。通過仿真實驗，單AP切換情況下的切換開銷得到極大改善，而多AP切換對比目前策略在系統吞吐率和AP負載均衡性方面都具有較好的性能。
本文的主要章節安排組織如下，第2節為公車網絡單AP切換策略，第3節為公車網絡多AP切換策略和AP選擇算法，第4節為切換策略的性能評估，第5節為下一步開展的工作。
2　公車網絡單AP切換——S-Handoff
由于公車的移動線路固定，下一個AP的的位置、信道號和MAC地址可以提前由SWC告知公車。結合對公車移動速度的估計，車輛可以估計出進入下一站點AP覆蓋范圍的時間及在兩個AP共同覆蓋的區域內的過渡時間Tt，這個Tt被當作切換被出發的時間。當來自兩個AP的SNR值接近相等時，切換就準備開始了。切換被觸發后，公車可根據信道號和MAC地址自行切換到下一AP，從而免去了切換過程中最耗費時間的信道掃描過程�；�于此，本文提出一種單AP切換策略——S-Handoff。

圖3 S-Handoff切換流程
S-Handoff的切換流程如圖3所示。S-Handoff的執行是通過公車主動探測下一AP的信道而展開的。切換過程需要完成的工作包括：
（1） 公車首先廣播探測消息——ProbeReq. 下一AP收到ProbeReq后向公車發送ProbeRes。
（2） 因為接到了AP發來的ProbeRes消息，公車記錄下一AP 的標識號，并向當前AP發送一個HoffNotify消息，其中包括該下一站點AP的標識號。
（3） 在收到HoffNotify消息后，當前AP通過有線網絡向下一AP發送一個切換準備好的消息。該消息包括公車的IP和MAC地址，其余的標識和數據包此時尚未傳送給公車。
（4） 當下一AP 收到切換準備好了的消息后，即將該公車加入公車列表。之后下一站AP發送一個切換成功的消息給當前AP，在收到切換成功的消息后當前AP 發送一個ACK幀——HdoffAck，告訴當前AP將公車從當前列表中刪除。
至此，切換過程完成，公車與當前AP 交換數據進行通信。
3　公車網絡多AP切換——M-Handoff
3.1　M-Handoff
由于公車事先已經知道沿途各站點的AP部署情況，當車輛進入一個站點，且其下一公交站點擁有多個AP時，公車首先向當前AP發起一個通告消息NotifyMsg，包含該車輛的帶寬需求。當前AP接收到該消息之后，通過有線網絡將該消息傳遞給下一站點的主AP。主AP先等待Twait時間，針對該時間內所有收到的通告消息NotifyMsg根據3.2節中的AP選擇算法決策出哪一個AP是該公車在下一站所要接入的AP，并將該結果以消息NotifyReply的形式通過有線網絡回復給當前AP。然后，當前AP將NotifyReply發送給車輛。上述過程中，一旦主AP開始決策 ，將不再把新到達的同一站點的通告消息納入當前決策的考慮范圍內。
當車輛進入到當前站點和下一站點的中間位置時即發起切換過程。該切換的發起時機和過程與單AP切換類似。其切換流程圖4所示。

圖4 M-Handoff切換流程
3.2　AP選擇算法——BWT(Balancing With Throughput)
本節采用的AP選擇算法是基于整個站點所有AP的吞吐率和站點中各個AP負載的均衡綜合考慮的。其中“負載”定義為AP連接的各個公車占用的帶寬總和。公車在連接下一AP時的帶寬要求可以估計為公車與上一AP通信的平均連接速率。AP負載的均衡即是各個AP間負載的差異程度。差異越小，越均衡。AP負載越均衡，就越可以最大化利用系統的帶寬資源和提高AP的工作效率。
AP負載均衡應以保證系統吞吐率為前提。這里的“系統吞吐率”定義為本站所有AP單位時間內的通信量的總和，越高的系統吞吐率說明了站點帶寬利用率越高，滿足了更多車輛的接入請求。如果AP能足夠應對多個有可能同時到達車輛的帶寬需求，AP可以在滿足帶寬要求的基礎上以更高的效率為車輛提供更高的帶寬。隨著車輛上客戶端的增多，殺手級應用的出現，信道數的制約等等原因，系統最終極有可能出現無法完全滿足各個車輛的情況。這就需要統籌車輛對AP的接入策略，以保證系統的吞吐率。如果只追求AP負載的均衡，那么可能出現AP拒絕很多車輛的接入要求的情況。而此時若不考慮系統吞吐率而單純追求AP負載的均衡是沒有意義的。所以本文優先保證系統較大的吞吐率可使AP滿足更多車輛的接入需求，繼而再均衡各AP的負載。
3.2.1　問題描述
本節為了便于描述問題，定義所涉及的符號如表1所示。
表1 問題描述所用符號定義
L AP的負載
W 公車的帶寬要求（可估計為當前時段的帶寬）
A；a 單個站點中AP的集合；a∈A
C；c 接入單個AP上所有公車的集合；c∈C
n 連接單個站點的公車數量，|C|=n
Wc 車輛c的帶寬要求
WC 接入單個AP的所有車輛C的帶寬要求
Bmax AP的最大帶寬，所有AP均相同
Twait 主AP決策等待時間
m 單個站點AP的數量
La a當前所連接用戶帶寬的總和，即a的負載
S；Sp 公車系統中站點的集合；Sp∈S
L a1、L a2、……、Laq、……、Lam 單個站點中各個AP的負載；1≤q≤m
表1中， Twait由歷史數據確定，其值為在線路上與該站相鄰的每一站點的車輛單次接入時間的最小值，對任一站點來講，該時間的值隨時間段的不同而改變，其值可保存在本站主AP中（本文實驗部分假設所有AP的該值相同），該時間保證了在決策完成并通知車輛之前，不會有車輛行使到當前AP邊緣而需要發生切換，并可以集中決策多個請求，更好的達到一段時間內的全局最優決策。
公車網絡中，系統吞吐率達到最大情況下的負載均衡問題可歸結為一個線性規劃問題：
s.t.
(1)
(2)
(3)
(4)
以上約束條件中，(1)是要保證系統吞吐率最大，而(2)－(4)是顯而易見的。
求解上述問題，首先要求解滿足系統吞吐率最大的所有接入情況，而后排除AP的負載超過最大承受能力的解，最后在剩下的解中，尋找所有AP的負載方差最小的那個解。這個求解過程是一個NP難問題[11]，其中求解系統最大吞吐率的解是一個“多背包問題”，也是一個NP難問題。整個問題的求解具有相當高的復雜度。因此，本文提出了一種啟發式算法——BWT，來降低問題的復雜度。
3.2.2 BWT（Balancing With Throughput）算法
在t時刻，Sp+1站主AP接到通告消息表示車輛c已接入站點Sp并發出通告消息，帶寬要求為Wc，主AP將等待Twait時間后開始決策。此時有兩種情況：
（1）如果在Twait時間內，主AP沒有再收到關于接入站點Sp+1的通告消息
主AP查詢得知現在站點Sp+1的各AP的負載為L p1、L p2、……、Lpq、……、Lpm，首先保證Wk+ Lpq≦Bmax；再找出負載最小的AP，即為下一站接入的AP，此時負載最均衡。
（2）如果在Twait時間內，主AP收到了其他車輛接入站點Sp+1的通告消息

BWT算法中主AP處理一個通告消息時，算法計算復雜度為O(2m)，m為本站AP個數。BWT算法中，主AP同時處理n輛公車的通告消息時，算法計算復雜度為O(n（m2+n+1）)，而NP難問題的計算復雜度為O（2mn）。BWT算法求近似解的計算復雜度要遠小于NP-hard問題的計算復雜度。BWT這種優先滿足大的請求的算法屬于一種“貪心算法”，是“多背包問題”常見的啟發式算法，可以保證比較大的系統吞吐率。該算法將較大帶寬請求的公車接入最輕負載的AP，也保證了各AP負載在一定程度上的均衡。
4　性能評估
本文采用NS-2模擬平臺對以上提出的兩種切換策略S-Handoff和M-Handoff進行性能評估。
對于S-Handoff，切換時延為主要考察的性能指標。本節將S-Handoff的性能與IEEE 802.11g標準的基于SNR的切換方法進行比較。
對于M-Handoff，因為主要工作在于AP的選擇，所以本文選擇系統吞吐率和AP負載均衡性為衡量性能的指標。系統吞吐率是單個站點所有AP在單位時間內的數據傳輸量。AP的負載是AP在單位時間內傳輸的數據量，AP的負載均衡采用各個AP負載的差值的大小來衡量。對比采用BWT算法選擇AP 和采用IEEE802.11p默認的基于SNR優先的方法自動選擇AP的系統吞吐率和兩個AP的負載均衡情況。
4.1　實驗場景
建立一條長3000m的公路，每隔250米設置一個公交車站，可以得到一共12個公交車站。隨機在12個站點中設置每個站點的AP數量情況。為了簡單起見，本文設置兩種AP數量，即1個和2個。如果一個站點有兩個AP，則設置距離為5m，4輛公車以10km/s~40km/s的隨機速度沿直線同向運動，當運動至公路末端時再反向運動。MAC協議采用IEEE 802.11g，兩個AP采用不同的信道與車輛通信，4輛車分別要求以8Mbps、10 Mbps、13Mbps、6Mbps的速率進行通信。仿真時間為600s。Twait在此取20s。實驗場景如圖5所示。

圖5 實驗場景示意圖
4.2　實驗結果

（1）S-Handoff性能
圖6顯示S-Handoff的切換開銷性能圖。如圖所示，采用S-Handoff切換策略的切換時延要明顯好于基于SNR的切換策略。由于S-Handoff無需信道掃描，所以相比基于IEEE 802.11g的切換的切換時延大大減少。

圖6 S-Handoff切換時延
由圖可以看出，傳統的基于802.11g的SNR切換切換開銷為平均360ms。而S-Handoff的切換開銷僅為22ms。
（2）M-Handoff性能
采用M-Handoff切換策略時，按照BWT算法，帶寬要求為13Mbps、6Mbps的與帶寬要求為10Mbps、8Mbps的公車將分別接入不同的AP；按照IEEE 802.11g協議的規定，客戶自動選擇AP的結果是帶寬要求為13Mbps、6 Mbps、10 Mbps的公車都接入了AP1。采用BWT算法選擇AP后的吞吐率一直高于基于SNR的高低自動選擇AP，如圖7所示。

圖7 系統的吞吐率 圖8 AP負載的均衡

采用BWT算法后兩個AP負載的差值要明顯低于自動選擇AP時的情況，如圖8所示。實驗結果表明，采用BWT算法選擇AP后的系統吞吐率和AP負載的均衡水平均要好于自動選擇AP的方式。BTW算法保證了系統吞吐率和AP負載的均衡性，達到了設計要求，可以在公車網絡中承擔多AP站點的AP選擇任務。
5　總結和未來工作
本文提出的兩種切換策略有效的改善了公車網絡的切換性能，為公車網絡的實際搭建提供了理論基礎。下一步打算就M-Handoff策略中BWT算法的解與最優解在不同AP數量中的逼近程度進行考察，并進一步優化BWT算法。另外，開展多AP切換中多AP同時連接的研究工作，豐富多AP切換的連接方式，找到更適合公車網絡的切換方法也將成為我們的下一步工作。
參考文獻 (References)
[1] J. Eriksson, H. Balakrishnan and S. Madden, “Cabernet: vehicular content delivery using WiFi”, in Proc. ACM MOBICOM, 2008, pp. 199-210.
[2] H. Wu, K. Tan, Y. Zhang, and Q. Zhang, “Proactive scan: Fast handoff with smart triggers for 802.11 wireless LAN,” in Proc. IEEE INFOCOM, Anchorage, AK, May 2007.
[3] Thomas King, Mikkel Baun Kjærgaard, “Composcan: adaptive scanning for efficient concurrent communications and positioning with 802.11”, in Proc. ACM MobiSys, 2008, pp.67-80.
[4] I. Ramani and S. Savage, “Syncscan: practical fast handoff for 802.11 infrastructure networks.” in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005.
[5] I. Papanikos and M. Logothetis, “A study on dynamic load balance for IEEE 802.11b wireless LAN,” in Proc. COMCON, 2001.
[6] A. Balachandran, P. Bahl, and G. M. Voelker, “Hot-spot congestion relief and service guarantees in public-area wireless networks,” ACM SIGCOMM Comput. Commun. Rev., vol. 32, no. 1, pp. 59–59, 2002.
[7] T.-C. Tsai and C. BALACHANDRAN A,BAHL A,VOELKER G.Hot-spot congestion relief in public area wireless network. In WMCSA 2002. New York, USA, Jone 20 – 21, 2002[C]. Washington:IEEE, 2002.195-205.
[8] ALBINALIL F,BODDUPALLIL P,DAVIESL N. An inter-access point handoff mechanism for wireless network management;the sabino system. In the 2003 International Conference on Wireless Network Nevada, USA, Jone 23 – 26, 2003[C]. Washington: IEEE, 2003.225-230.
[9] BALACHANDRAN A,BAHL A,VOELKER G.Hot-spot congestion relief in public area wireless network. In WMCSA 2002. New York, USA, Jone 20 – 21, 2002[C]. Washington:IEEE, 2002.195-205.
[10]Aruna Balasubramanian, Ratul Mahajan, Arun Venkataramani, Brian Neil Levine, John Zahorjan. Interactive WiFi Connectivity For Moving Vehicles. In SIGCOMM’08, Seattle. Washington: ACM, 2008.
[11]Yigal Bejerano, Seung-Jae Han, Li (Erran) Li. Fairness and Load Balancing in Wireless LANs Using Association Control. IEEE/ACM TRANSACTIONS ON NETWORKING, 2007, VOL. 12, NO. 3: 560.

作者簡介：劉海東(1983－)，男，遼寧遼陽市人，碩士生，主要研究領域為車載網絡，移動計算；徐明(1964－)，男，博士，教授，主要研究領域為無線網絡，移動計算；匡羅貝(1983－)，男，博士生，主要研究領域為車載網絡，移動計算。