通信网络理论与道路网络理论关键节点分析的对比研究
|
摘要
近年来,人均汽车保有量不断上涨,虽然部分大中型城市采取了尾号限行的措施,但是交通拥堵的状况依然愈演愈烈。尤其是早晚高峰期间及节假日的庞大交通流量使得负荷早已接近饱和的道路网络系统濒临崩溃。交通拥堵不仅造成了一定的经济损失,并且在堵塞过程中产生了大量的环境污染。出于减轻交通拥堵的状况,减少不必要的燃油空耗、尾气污染的目的,如何提高道路网络的可靠性,降低因节点拥堵造成的局部网络瘫痪可能性,已成为专家学者研究的热门课题。
在学者们对于道路交通网络的长期观察研究中发现,道路网络作为一个整体,在实际情况下,拥堵的产生并非随机分布毫无规律可循的,而是主要由于某些交叉路口或路段的拥堵造成了一定范围的路网瘫痪,因此对于路网中的这些交叉路口和路段进行分析至关重要。
从二十世纪70年代开始,对于网络中节点重要性的研究就已经开始。通过研究各种网络的抽象拓扑结构,借助于网络中节点的度、介数,节点生成树,最短路径等属性特征,量化地研究网络中各个节点的重要性差别。然而这些研究都侧重于网络拓扑图的结构属性,而道路网络存在自身的一些特征,例如：地理位置信息,交通流量,车流速度等。这些特征使得上述研究并不能与道路网络中关键节点的发掘完全契合。
为解决上述问题,本文在对通信网络和道路网络中关键节点研究方法总结、对比和分析的基础上,提出了研究道路网络中的关键节点首先需要明确网络的功能并以此确定网络中关键节点的这一解决问题的方法,明确关键节点定义从而确定道路网络中节点重要性的评价标准,即道路网络中易受损和易引起其他节点和大面积路网瘫痪的节点为关键节点。由此提出了路网中关键节点分析的特色算法,并选取经典路网模型Sioux Falls进行分析研究,验证了所提出算法的合理性和实用性。
In recent years, with the increasing of car ownership per capital, the traffic congestion is more and more intensive, even though there is tail number limited in some large and medium-sized city. Especially morning and evening rush hours and holidays, the huge traffic load makes the road network near to collapse, which is already saturated. The traffic congestion makes not only economic losses but also widespread contamination. In order to reduce traffic congestion, fuel consuming and gas pollution, it has become a hot topic to researchers that how to improve the reliability of road network and to reduce the possibility of local road network paralysis caused by node jam.
In the long term study and observation of road network, researchers found that the congestion in the network does not generate randomly and irregularly, in the actual situation, but caused by the certain nodes or links. Therefore, the study of the key nodes and links is significant.
Since1970s, research on the key nodes in the network has been put forward. Through studying the abstract topology structure of various network and based on the degree, betweeness, shortest path, spanning tree of network, the importance of nodes is discriminatingly quantified. However, these researches focused more on topological characteristics of road networks. The road network has some own characteristics such as geographical position information, traffic flow, traffic velocity and so on. These features make the above researches not match the study of key nodes in the road network that much.
To solve above questions, based on the summary, comparison and analysis of communication network and road network, the solution is put forward that the function of road network and the definition of key nodes should be clear-cut firstly and determine the evaluation criterion of nodes' importance. The definition of key nodes is that the key nodes should be the vulnerable ones and which make other nodes failed and local road network paralysis more easily than others. The special algorithm of key node analysis in the road network is proposed, and the classic road network, Sioux Falls, as numerical experiment is provided to demonstrate the practice and accuracy of the solution.
在学者们对于道路交通网络的长期观察研究中发现,道路网络作为一个整体,在实际情况下,拥堵的产生并非随机分布毫无规律可循的,而是主要由于某些交叉路口或路段的拥堵造成了一定范围的路网瘫痪,因此对于路网中的这些交叉路口和路段进行分析至关重要。
从二十世纪70年代开始,对于网络中节点重要性的研究就已经开始。通过研究各种网络的抽象拓扑结构,借助于网络中节点的度、介数,节点生成树,最短路径等属性特征,量化地研究网络中各个节点的重要性差别。然而这些研究都侧重于网络拓扑图的结构属性,而道路网络存在自身的一些特征,例如：地理位置信息,交通流量,车流速度等。这些特征使得上述研究并不能与道路网络中关键节点的发掘完全契合。
为解决上述问题,本文在对通信网络和道路网络中关键节点研究方法总结、对比和分析的基础上,提出了研究道路网络中的关键节点首先需要明确网络的功能并以此确定网络中关键节点的这一解决问题的方法,明确关键节点定义从而确定道路网络中节点重要性的评价标准,即道路网络中易受损和易引起其他节点和大面积路网瘫痪的节点为关键节点。由此提出了路网中关键节点分析的特色算法,并选取经典路网模型Sioux Falls进行分析研究,验证了所提出算法的合理性和实用性。
In recent years, with the increasing of car ownership per capital, the traffic congestion is more and more intensive, even though there is tail number limited in some large and medium-sized city. Especially morning and evening rush hours and holidays, the huge traffic load makes the road network near to collapse, which is already saturated. The traffic congestion makes not only economic losses but also widespread contamination. In order to reduce traffic congestion, fuel consuming and gas pollution, it has become a hot topic to researchers that how to improve the reliability of road network and to reduce the possibility of local road network paralysis caused by node jam.
In the long term study and observation of road network, researchers found that the congestion in the network does not generate randomly and irregularly, in the actual situation, but caused by the certain nodes or links. Therefore, the study of the key nodes and links is significant.
Since1970s, research on the key nodes in the network has been put forward. Through studying the abstract topology structure of various network and based on the degree, betweeness, shortest path, spanning tree of network, the importance of nodes is discriminatingly quantified. However, these researches focused more on topological characteristics of road networks. The road network has some own characteristics such as geographical position information, traffic flow, traffic velocity and so on. These features make the above researches not match the study of key nodes in the road network that much.
To solve above questions, based on the summary, comparison and analysis of communication network and road network, the solution is put forward that the function of road network and the definition of key nodes should be clear-cut firstly and determine the evaluation criterion of nodes' importance. The definition of key nodes is that the key nodes should be the vulnerable ones and which make other nodes failed and local road network paralysis more easily than others. The special algorithm of key node analysis in the road network is proposed, and the classic road network, Sioux Falls, as numerical experiment is provided to demonstrate the practice and accuracy of the solution.
引文
[1]刘丹DYK公司发展战略研究[学位论文]苏州苏州大学2011
[2]孙跃冬,亢敏,周萍 汽车工业发展与公路交通建设上海理工大学学报：社会科学版27(1)2005 58-62
[3]张权勋国家机动车污染控制研究技术中心(厦门)项目可行性研究[学位论文]厦门厦门大学2005
[4]白锦会,戴志松 熵理论研究的进展和意义华中师范大学学报：自然科学版24(1)1990.3 118-125
[5]李一蒙最大熵算法在SNP与疾病关联性研究的应用[学位论文]西安西安电子科技大学2011
[6]维基百科熵http://wiki.pinggu.org/doc-view-36501.html
[7]胡满玉基于链接关系的有向加权复杂网络关键节点识别技术[学位论文]南京南京理工大学2012
[8]唐雄燕 电信技术的发展与传统电信网络革新电信技术2002(1)2002 34-35
[9]唐殿奎区域交通控制的分析与研究[学位论文]济南济南大学2010
[10]李菲,肖红翔城市交通路网数据模型的构建及其拓扑结构的研究科学技术与工程9(8)2009.4 2211-2214
[11]姚玉斌基于邻接矩阵准平方法网络拓扑分析电力系统保护与控制40(6)2012.317-29
[12]刘龙廿 基于双层动态均衡原理的交通网络设计模型及方法[学位论文]重庆重庆交通大学2010
[13]郭红,兰巨龙,刘洛琨 考虑节点重要度的AdHoc网络抗毁性测度研究小型微型计算机系统31(6)2010.6 1063-1066
[14]饶育萍,林竞羽,侯德亭基于最短路径数的网络抗毁评价方法通信学报30(4)2009.4 113-117
[15]钟书华物联网演义(三)——IBM的“智慧地球”物联网技术2012(7)2012 86-87
[16]李世伟有权复杂网络的演化模型机重要节点的研究[学位论文]合肥合肥工业大学2010
[17]赫南,李德毅,淦文燕等复杂网络中重要性节点发掘综述计算机科学34(12)2007.12 1-5
[18]Albert R, Jeong H, Barabasi A L Error and Attack Tolerance of Complex Network. Nature 406(27) 2000 378-382
[19]Reuven C, Keren E, Daniel B, et al. Resilience of the Internet to Random Breakdowns. Phys Rev Lett 85(21) 2000 4626-4628
[20]Corley H, sha D. Most Vital Links and Nodes in Weighted Networks. Operations Research Letters 1(4) 1982 157-160
[21]Nardelli E, Proietti G, Widmayer P. Finding the Most Vital Node of a Shortest Path. Proc of Computing and Combinatorics 2001
[22]Cruclt ti P, Latora V, Marchiori M, et al. Efficiency of scale-free networks:Error and attack tolerance. Physica A320 2003 622-642
[23]Taylor, M.A.P, Sekhar, S.V.C., D'Este, G.M.. Application of accessibility based methods for vulnerability analysis of strategic road networks. Network & Spatial Economics 6 2006 267-291
[24]Liu Jianqiang, Lan Julong, Wu Jiangxing. Evaluating the Vital Network Nodes Based on Node Estranging. Computer Engineering & Science 33(3) 2011 13-17
[25]Tan Yuejin, Wu Jun, Deng hongzhong Evaluation Method for Node Importance based on Node Contraction in Complex Networks System Engineering-Theory & Paractice 11 2006 79-83
[26]郭瑞钟宁李文斌基于图熵的社会网络演化分析模式识别与人工智能22(3)2009.6 360-365
[27]王甲生吴晓平廖巍等改进的加权复杂网络节点重要度评估方法计算机工程38(10)2012.5 74-76
[28]杨汀依 复杂网络关键节点识别技术研究[学位论文]南京 南京理工大学2011
[29]项方产 基于通信关系的意见领袖挖掘与应用[学位论文]上海 上海交通大学2007
[30]余新,李艳和,郑小平等基于网络性能变化梯度的通信网络节点重要程度评价方法清华大学学报：自然科学版48(4)2008 541-544
[31]廖小琴,刘虹,孙建军 链接网络与核心节点评价指标研究综述情报杂志31(5)2012.5 166-171
[32]赵毅寰,王祖林,郑晶等利用重要性贡献矩阵确定通信网中最重要节点北京航空航天大学学报35(9)2009.9 1076-1080
[33]戴伏生通信网络各节点和链路重要性的客观评估方法南京理工大学学报30(6)2009.12 748-755
[34]高洁 交通运输网络节点重要度评价体系研究聊城大学学报：自然科学版23(3)2010.9 92-98
[35]沈鸿飞,贾利民,王笑京等基于公路网结构特性的关键节点评价指标与辨识方法公路交通科技29(9)2012.9 137-143
[36]宋永朝,潘晓东,陈聪等面向应急疏散的山区公路交通节点中国公路学报23(4)2010.7 102-108
[37]Kaufman Hall, Mecit Cetin. Estimating Queue Dynamics at Signalized Intersections from Probe Vehicle Data:A Methodology Based on Kinematic Wave Model. Transportation Research Record:Journal of the Transportation Research Board 500 Transportation Research Board of the National Academies, Washington, D.C.2012
[38]William J. Beaty. Traffic Experiments and A Cure For Waves & Jams, Electrical Engineer 1998. http://trafficwaves.org/trafexp.html
[39]B.Y. Chen et al. Vulnerability analysis for large-scale and congested road networks with demand uncertainty. Transportation Research Part A 46(2012) 501-516.
[40]流云哭翠几种最短路径算法的比较2012http://blog.chinaunix.net/uid-27164517-id-3287891.html
[41]王丰元,潘福全,张丽霞等.基于交通限制的路网最优路径算法交通运输工程学报5(1)2005.3 92-95
[42]赵淑芝,朱永刚,赵贝.居民交通出行OD预测研究交通运输系统工程与信息.10(2)2010.4 88-92
[43]最短路径选择算法http://www.5igis.com/algorithm/shortpath.htm
[44]Liu Maoli, Deng Zhongliang. A Choosing Leader Based Vulnerability of Complex Networks. Ship Electronic Engineering 31(1) 2011 113-115
[2]孙跃冬,亢敏,周萍 汽车工业发展与公路交通建设上海理工大学学报：社会科学版27(1)2005 58-62
[3]张权勋国家机动车污染控制研究技术中心(厦门)项目可行性研究[学位论文]厦门厦门大学2005
[4]白锦会,戴志松 熵理论研究的进展和意义华中师范大学学报：自然科学版24(1)1990.3 118-125
[5]李一蒙最大熵算法在SNP与疾病关联性研究的应用[学位论文]西安西安电子科技大学2011
[6]维基百科熵http://wiki.pinggu.org/doc-view-36501.html
[7]胡满玉基于链接关系的有向加权复杂网络关键节点识别技术[学位论文]南京南京理工大学2012
[8]唐雄燕 电信技术的发展与传统电信网络革新电信技术2002(1)2002 34-35
[9]唐殿奎区域交通控制的分析与研究[学位论文]济南济南大学2010
[10]李菲,肖红翔城市交通路网数据模型的构建及其拓扑结构的研究科学技术与工程9(8)2009.4 2211-2214
[11]姚玉斌基于邻接矩阵准平方法网络拓扑分析电力系统保护与控制40(6)2012.317-29
[12]刘龙廿 基于双层动态均衡原理的交通网络设计模型及方法[学位论文]重庆重庆交通大学2010
[13]郭红,兰巨龙,刘洛琨 考虑节点重要度的AdHoc网络抗毁性测度研究小型微型计算机系统31(6)2010.6 1063-1066
[14]饶育萍,林竞羽,侯德亭基于最短路径数的网络抗毁评价方法通信学报30(4)2009.4 113-117
[15]钟书华物联网演义(三)——IBM的“智慧地球”物联网技术2012(7)2012 86-87
[16]李世伟有权复杂网络的演化模型机重要节点的研究[学位论文]合肥合肥工业大学2010
[17]赫南,李德毅,淦文燕等复杂网络中重要性节点发掘综述计算机科学34(12)2007.12 1-5
[18]Albert R, Jeong H, Barabasi A L Error and Attack Tolerance of Complex Network. Nature 406(27) 2000 378-382
[19]Reuven C, Keren E, Daniel B, et al. Resilience of the Internet to Random Breakdowns. Phys Rev Lett 85(21) 2000 4626-4628
[20]Corley H, sha D. Most Vital Links and Nodes in Weighted Networks. Operations Research Letters 1(4) 1982 157-160
[21]Nardelli E, Proietti G, Widmayer P. Finding the Most Vital Node of a Shortest Path. Proc of Computing and Combinatorics 2001
[22]Cruclt ti P, Latora V, Marchiori M, et al. Efficiency of scale-free networks:Error and attack tolerance. Physica A320 2003 622-642
[23]Taylor, M.A.P, Sekhar, S.V.C., D'Este, G.M.. Application of accessibility based methods for vulnerability analysis of strategic road networks. Network & Spatial Economics 6 2006 267-291
[24]Liu Jianqiang, Lan Julong, Wu Jiangxing. Evaluating the Vital Network Nodes Based on Node Estranging. Computer Engineering & Science 33(3) 2011 13-17
[25]Tan Yuejin, Wu Jun, Deng hongzhong Evaluation Method for Node Importance based on Node Contraction in Complex Networks System Engineering-Theory & Paractice 11 2006 79-83
[26]郭瑞钟宁李文斌基于图熵的社会网络演化分析模式识别与人工智能22(3)2009.6 360-365
[27]王甲生吴晓平廖巍等改进的加权复杂网络节点重要度评估方法计算机工程38(10)2012.5 74-76
[28]杨汀依 复杂网络关键节点识别技术研究[学位论文]南京 南京理工大学2011
[29]项方产 基于通信关系的意见领袖挖掘与应用[学位论文]上海 上海交通大学2007
[30]余新,李艳和,郑小平等基于网络性能变化梯度的通信网络节点重要程度评价方法清华大学学报：自然科学版48(4)2008 541-544
[31]廖小琴,刘虹,孙建军 链接网络与核心节点评价指标研究综述情报杂志31(5)2012.5 166-171
[32]赵毅寰,王祖林,郑晶等利用重要性贡献矩阵确定通信网中最重要节点北京航空航天大学学报35(9)2009.9 1076-1080
[33]戴伏生通信网络各节点和链路重要性的客观评估方法南京理工大学学报30(6)2009.12 748-755
[34]高洁 交通运输网络节点重要度评价体系研究聊城大学学报：自然科学版23(3)2010.9 92-98
[35]沈鸿飞,贾利民,王笑京等基于公路网结构特性的关键节点评价指标与辨识方法公路交通科技29(9)2012.9 137-143
[36]宋永朝,潘晓东,陈聪等面向应急疏散的山区公路交通节点中国公路学报23(4)2010.7 102-108
[37]Kaufman Hall, Mecit Cetin. Estimating Queue Dynamics at Signalized Intersections from Probe Vehicle Data:A Methodology Based on Kinematic Wave Model. Transportation Research Record:Journal of the Transportation Research Board 500 Transportation Research Board of the National Academies, Washington, D.C.2012
[38]William J. Beaty. Traffic Experiments and A Cure For Waves & Jams, Electrical Engineer 1998. http://trafficwaves.org/trafexp.html
[39]B.Y. Chen et al. Vulnerability analysis for large-scale and congested road networks with demand uncertainty. Transportation Research Part A 46(2012) 501-516.
[40]流云哭翠几种最短路径算法的比较2012http://blog.chinaunix.net/uid-27164517-id-3287891.html
[41]王丰元,潘福全,张丽霞等.基于交通限制的路网最优路径算法交通运输工程学报5(1)2005.3 92-95
[42]赵淑芝,朱永刚,赵贝.居民交通出行OD预测研究交通运输系统工程与信息.10(2)2010.4 88-92
[43]最短路径选择算法http://www.5igis.com/algorithm/shortpath.htm
[44]Liu Maoli, Deng Zhongliang. A Choosing Leader Based Vulnerability of Complex Networks. Ship Electronic Engineering 31(1) 2011 113-115