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－)，男，博士生，主要研究领域为车载网络，移动计算。