已有路网容量研究不能解决实时路网容量计算问题, 难以掌握实时路网中的实际运行车流; 传统的路网容量算法基本是离线处理或通过人工调查进行理论计算, 很难解决实时路网容量的难题, 为此, 提出了一种基于免疫理论的车联网城市路网实时容量新方法.该方法将免疫网络理论引入车辆自组织网络, 利用抗体识别抗原的原理, 完成通信链路检测, 同时, 可以通过统计抗原抗体识别对获取路网中的车流, 不仅解决了实时性问题, 还解决了传统方法需要建立准确数学模型的难题.选取了实际路网中的区域进行验证, 实验结果与传统方法获取的路网容量非常接近, 证明了该方法的有效性.
The road network capacity lays foundation of the intelligent transportation systems for developing the carrying capacity of road networks; it's no doubt important for traffic control, traffic guidance and traffic demand management. However, the existed work can not entirely solve the problem of real-time calculation of road network capacity, however, it is difficult to control the actual operation traffic flow by traditional road network algorithm, which is a theoretical calculation based offline processing or a survey carried out by manual. A new road network capacity method was proposed based on the vehicular self organization network based immune network theory. The theory completes communication link detections between vehicles and infrastructure, and then the antigen-antibody statistics can be performed for computing vehicles in the network when thinking the principle of antibody recognized antigen. The proposed method not only solves the real-time problem, but also solves the problem of the traditional methods requirements to establish an accurate mathematical model. Finally, an actual road network was selected for experimental verification. Experiments are very close to the capacity obtained with the traditional, and prove the effectiveness of the proposed method.
路网容量的研究已经有几十年的历史,呈现了很多研究成果,无论是在理论方法研究还是在实际工程应用方面,都得到了一定程度的应用.但目前的理论方法在实际交通工程中的应用还存在一定的困难,如实际应用中需要确定的模型或算法参数过多,还需凭借经验进行修正.在理论方法研究方面,时空消耗方法充分考虑了路网的几何特性和车辆出行的其他因素,虽然计算中待确定的参数较多,但其计算出的路网容量能与路网通行能力在理论上保持一致性,确保了时空消耗法的准确性[1].但由于此方法都是离线计算的,在其他方面应用受到极大限制,不能满足实时交通管理的要求,也不能满足实时路网状况监控管理方面的要求.在时空消耗法之后,对路网容量计算的研究出现了大量的算法,从各个方面进行改进或引入其他领域的算法解决路网容量计算的问题如线性规划模型法[2]、割集法[3]、交通流分配法[4]、供应分析法[5]、狭义路网容量分析法等[6].但无论是时空消耗法还是其后出现的算法,都是建立在确定的数学模型基础上,需通过大量实验获取模型参数,仍然是处理离线或事后计算的问题,对于实时性问题并不能解决.
目前实时路网容量在实时交通管理方面起着重要作用,通过实时掌握路网容量,有利于整个路网管理、交通流诱导.但已有路网容量计算方法的研究成果中,还未有一种有效的实时路网容量计算方法可以满足实时路网管理应用的要求.笔者针对传统路网容量计算方法存在的问题以及服务对象的变化,从离线计算到实时计算的变化,研究了车辆自组织网络在实时交通信息采集方面的应用,并引入免疫网络理论以解决传统方法数学建模的难题,提出一种新型的实时路网容量计算方法.
1 基于免疫理论的车联网的城市路网实时容量新方法1.1 免疫网络原理免疫理论是模仿自然免疫系统功能的一种人工智能方法,它实现一种受生物免疫系统启发,通过学习外界物质的自然防御机理的学习技术.
免疫网络理论将免疫系统视为由免疫细胞或者分子组成的调节网络,免疫细胞以抗体间的相互反应和不同种类免疫细胞间的相互通信为基础,抗原识别由抗原相互作用所形成的免疫网络完成.免疫网络原理包含2种抗体作用机制,即克隆抑制和抗体的动态平衡维持.克隆抑制是指突变的克隆群中相似及相同的抗体群确定性地抑制,促成产生具有相似度较低及细胞种类较多的免疫细胞群.动态平衡维持是指当前免疫细胞群与克隆细胞群共同竞争,体现抗体之间相互抑制和相互促进机理,此外随时产生自我抗体插入存活的抗体群,使免疫系统中抗体的总数目得到控制,同时多种抗体的数目达到平衡.通过这2种机制调节网络的稳定性,也使免疫系统保持多样性.
通过引入免疫网络原理,提出算法框架.
1.2 算法框架基于人工免疫系统(AIS, artificial immune system)的算法借鉴了免疫系统的抗体识别抗原,并在B细胞产生新抗体,T细胞抑制B细胞的无限制增长,使得系统处于稳定的状态.提出的算法框架如图 1所示.通过免疫应答,抗原被抗体识别并吞噬,如果已有抗体不能识别抗原,免疫系统会刺激B细胞增长产生新的抗体,进行二次免疫应答.
为了将免疫网络理论应用于实时路网容量计算中,首先进行基本的定义,为算法流程实现奠定基础.
定义1 抗原(Ag):在免疫系统中,抗原是入侵免疫系统的外来病原物质.在路网模型中,抗原定义为路网中运行的车辆.路网中的车辆也就是需要识别的物质,即抗原,表示为Ag:Ag={Ag1, Ag2, …, Agn}.
定义2 抗体(Ab):在免疫系统中,抗体是系统自身的产物,是由B细胞生成的物质,是识别抗原并吞噬抗原的物质.在文中将路边设施定义为抗体,表示为Ab:Ab={Ab1, Ab2, …, AbNAb}(NAb为抗体种群数量).
定义3 相似抗体数据(sAb):在路网模型中,把路网中车辆称为相似抗体数据,表示为sAb:sAb={sAb1, sAb2, …, aAbp},sAb⊂Ag.
定义4 亲和度(AAg.Ab):在路网模型中,把Ag和Ab之间的通信连接成功的概率函数(用S(Ag, Ab)表示)看作免疫系统中抗原和抗体的结合程度,称为亲和度,表示为AAg.Ab.若抗原与抗体之间通信成功,则S(Ag, Ab)的值较大,否则S(Ag, Ab)的值较小,且S(Ag, Ab)∈[0, 1]. Ag和Ab连接成功概率越大,亲和度越大,反之越小.定义亲和度为
(1) |
根据图 1中的AIS框架,免疫应答算法利用了免疫应答的机制识别路网中车辆数.在算法执行过程中进行以下处理.
混沌序列生成:混沌序列具有很好的遍历性和随机性,因此,在所提出的算法中,抗体种群产生采用混沌序列方法.混沌序列生成按式(2) 进行.
(2) |
其中:μ为控制参数,xn为时间序列.当μ确定后,对于任意初始值x0∈[0, 1],可以迭代出一个确定的时间序列(x1, x2, x3…).当0<μ≤1时,系统很简单;当1<μ≤3时,系统也比较简单;当3<μ≤4时,系统十分复杂,系统逐步混沌化;当μ>4时,系统更为复杂,完全处于混沌状态.
亲和度计算:按照式(1) 计算Agi和Ab种群的亲和度.
克隆选择:克隆选择是为了保证抗体数据的多样性,对具有最高亲和度的抗体数据进行克隆选择,产生新抗体.克隆选择算子为
(3) |
其中:Nc为克隆的数量,α为克隆选择概率,round(·)表示取整函数.
混沌变异:按照变异率β,对克隆选择的抗体数据根据式(2) 来变异,保证抗体数据的多样性.
算法流程如下.
输入:Agi(i=1, 2, …, n)和路网中相关信息.
输出:路网中进行通信连接成功的行驶车辆ID统计数.
步骤1 混沌初始化:初始化抗体数据种群,Ab={Ab1, Ab2, …, AbIAb},其中IAb为初始抗体种群数量.
步骤2 对每个抗原数据Agi:① 按式(1) 计算亲和度;② 按计算的亲和度,对具有最高亲和度的抗体数据进行克隆选择,克隆选择按式(3) 进行;③ 按变异率β对克隆体进行式(2) 所示的混沌变异.
步骤3 若通信连接成功,记录能被识别Agi的编号,并计数.
步骤4 抑制:删除相似抗体sAb.
步骤5 多样性:在算法执行中,比较抗体数,若NAb<IAb,则产生(IAb-NAb)个新抗体数据.
步骤6 如果都未满足终止条件,则跳转至步骤2;否则,算法终止.
算法终止条件:对于新抗原,步骤2至步骤5计算过程成立,则算法终止;否则产生新抗体,重新进行步骤2至步骤5计算.
1.3.1 抗体种群的产生抗体种群的产生既要满足抗体数量的要求,又要满足算法计算快速的要求.在以往免疫网络算法中,抗体种群产生一般采用随机序列的方法,虽然简单,但也存在一定的问题.而混沌序列具有很好的遍历性和随机性,所以采用混沌序列的方法产生抗体种群,具体产生方式如式(2) 所示.
1.3.2 增加新抗体数据为了保证算法的有效性,既可以保证抗体的多样性,又不至于增加算法的计算量.首先计算抗体种群的规模,即NAb,如果NAb>IAb,那么不产生任何新抗体数据,否则产生(IAb-NAb)个新的抗体数据.这样,既删除了无用的抗体数据,又有节制地增加了新的抗体数据,丰富了抗体种群的多样性.新抗体增加的计算公式为
(4) |
为了对比分析所提出的新方法与传统方法的有效性,选择学院南路大柳树路到新街口外大街之间的路段区域进行实例研究,研究区域如图 2所示.
首先进行人工数据采集,采用摄像机进行路段断面拍摄的方法采集数据.研究区域可以划分为5个路段断面,在各路段断面选择合适的区域并在同一时间采用摄像机拍摄的方式进行数据采集.采集了2012-11-14(周三)17:00—18:00内各路段断面的视频数据,并通过视频数据处理,获取各个断面的交通流数据,如表 1所示.其中交通流数据以私家小汽车(PCU, personal car unit)为单位.
新街口外大街到大柳树路之间路段总长3 054 m,双向4车道,按时空消耗法计算,此间单向路网总时空资源为
(5) |
其中:L为路网的总长度,d为道路的车道宽度或车道数,t0为数据采集起始时间,t1为数据采集终止时间.
而1辆车在1次出行时段内消耗的路网资源为
(6) |
其中:h为车头距离,d′为车辆宽度,l′为车辆长度,t为出行时间.通过多次实验测量和车牌过境统计,从新街口外大街到大柳树路车辆平均出行时间为15.1 min,即可算出每辆车出行时段消耗的路网资源.假设平均车辆长度为4 m,则每辆车在此路网上的出行时段路网资源消耗为4 m×1×15.1 min,在时空消耗方法中,路网容量即为
(7) |
传统路网容量计算方法如交通分配法是采集路网各路段的流量,反推路段车辆出行的起点和终点,然后通过交通规划软件TransCAD进行路网流量分配计算.虽然路网流量可以通过路段中安装的线圈或视频装置进行自助统计,但目前大部分安装设备都是单点工作模式,未进行联网操作,采集的数据需要进行人工处理才能进行TransCAD仿真.因此,将摄像机看作路边通信设施(抗体),本次实验中抗体数为5,那么,通过路段的车辆即为进入摄像场景的抗原,通过识别记录统计即可实时获取路段中实时运行车辆数量.
1) 抗体种群的产生
为了更好体现抗体的多样性,借鉴了混沌的遍历性和随机性,采用式(2) 来产生混沌序列.
2) 算法参数设置
算法测试需要对参数进行设置,一共为IAb、α、β 3个参数,3个参数不但影响算法的准确性,还影响算法的效率.经过多次测试实验,3个参数的取值范围如表 2所示.
通过30次仿真实验,抗原数据逐个地输入,仿真实验参数取值为α=0.2、β=0.3、IAb从50变化到1 000.通过不断的实验测试,选取IAb=100.在实验中新抗体产生数量按式(4) 计算,并执行1.3节给出的算法流程.
在仿真实验中,仿真工具选取了NS-2仿真软件,这是一种网络仿真工具.为了仿真更加逼近专用短程通信(DSRC, dedicated short range communications)的车联网实际环境,设置无线信号频率为5.9 GHz,带宽为10 MHz;并假设车辆通信天线为双向定向天线,传输功率为20.4 dBm,通信范围为400 m.根据标准,调整DSRC接收灵敏度为-77 dBm,采取IEEE 802.11MAC并设置数率为6 Mbit/s.仿真按照研究区域执行,车辆数在0~2 000之间,仿真时间为1 200 s,仿真次数为30次,所得结果为仿真次数的平均值.按照1.3节给出的算法流程,在抗体识别抗原后,记录被识别的抗原,自动计数被识别的抗原数,并按算法定义,抗原数即为在路网中实时行驶的车辆数,即可获取实时行驶在路网中的车辆数,即为实时路网容量.抗体识别抗原的统计计算公式为
(8) |
其中:Abi·Agj为抗体与抗原识别对,CR为计算出的实时路网容量.将每个抗体识别的抗原总数表示为Ci(i=1, 2, …, IAb),则式(8) 改写为
(9) |
通过实验仿真,对输出内容进行统计,计算出的实时路网容量为
比较时空消耗法和基于免疫网络理论的路网容量算法可以看出,计算得到的路网容量较相近.通过时空消耗法计算所得的路网容量接近路网的理论容量值,而通过基于免疫网络理论的路网容量算法计算获得的路网实时容量是在路网中实时行驶的车辆,但算法会出现一定的计算误差,其原因在于基于免疫网络理论的路网容量算法存在重复统计的现象,有待进一步改善和大量实际交通环境的验证.
在算法中的3个参数IAb、α、β,可以通过平均运行时间和正确率对其变化进行分析,进而分析它们对算法的影响.正确率是算法在运行中对车辆识别的衡量,即在识别统计中有可能存在漏识别或重复统计的情况.当测试IAb对算法的影响时,其他参数取固定值.当IAb增加时,意味着抗体数据增多,必然会使计算量增加,即算法的运行时间变长. IAb的增加也意味着在数据空间中存在更多的抗体识别新增的抗原数据,即识别的准确率越高.通过实验仿真,结果如图 3和图 4所示,由仿真结果可以看出参数对结果的影响.
由仿真实验和结果分析可以看出,IAb、α、β3个参数的设置对结果具有一定程度的影响,参数α和β的作用与IAb有很大的相同之处,故不讨论其对算法的影响.
通过实验结果分析,基于免疫网络理论的路网容量算法与传统的时空消耗法相比,不但可以实时统计路网行驶车辆数据,而且准确性也与时空消耗法所得路网容量相近.时空消耗法得出几乎是路网容量的理论值,基于免疫网络理论的路网容量算法与理论值比较接近,这与当天的路网运行状况相符.基于免疫网络理论的路网容量算法不需要建立准确的数学模型,计算复杂度低,并实时联网,为车联网用于智能交通系统领域奠定了基础,并通过实验证明了基于免疫网络理论的路网容量算法是有效并实用的.
3 结束语通过对比分析目前已有的路网容量计算方法的优缺点,将免疫网络理论引入到路网容量研究领域,利用免疫网络理论抗体识别抗原的原理,统计抗体识别抗原对,获取路网中实时运行的车辆信息,提出了基于免疫网络理论的车联网的城市路网实时容量计算的新方法.通过选取实地场景进行实验验证,基于免疫网络理论的路网容量算法效果上与传统的方法可媲美,实施上在基于车辆自组织网络是非常容易可靠的,为车辆自组织网络的实际应用开辟了新的方向,也为交通管理部门对实时控制城市路网运行提供了可行的方法.
[1] | Ma Jianxiao. Study on urban local traffic network capacity[D]. Nanjing: Nanjing Forestry University, 2007. |
[2] | Zuo Zhongyi, Li Jian, Jin Xiaoqiong, et al. Research on road network capacity based on resource used ratio[J].Journal of Dalian Jiaotong University, 2013, 34(3): 47–50. |
[3] | Bruno R, Nurchis M. Robust and efficient data collection schemes for vehicular multimedia sensor networks[C]//IEEE 14th International Symposium and Workshops on a World of Wireless, Mobile and Multimedia Networks (WoWMoM). Madrid: IEEE Xplore, 2013: 1-10. |
[4] | Yan Huang, Xin Guan, Cai Zhipeng, et al. Multicast capacity analysis for social-proximity urban bus-assisted VANETs[C]//2013 IEEE International Conference on Communications (ICC). Xi'an: IEEE Xplore, 2013: 6138-6142. |
[5] | Wang Cheng, Jiang Changjun, Li X Y, et al. Scaling laws of multicast capacity for power-constrained wireless networks under gaussian channel model[J].IEEE Transactions on Computers, 2013, 61(5): 713–725. |
[6] |
李清平, 周鹏. 基于链路容量算法的集中式计算机网络优化[J]. 北京信息科技大学学报, 2013, 28(4): 24–28.
Li Qingping, Zhou Peng. An optimal algorithm of link circuit capacity for centralized computer network[J].Journal of Beijing Institute of Machinery, 2013, 28(4): 24–28. |