解决高度分割的车载自组网络连通性问题的路侧单元最优化调度方案

J4 ›› 2012, Vol. 34 ›› Issue (1): 1-10.

• 论文 • 下一篇

解决高度分割的车载自组网络连通性问题的路侧单元最优化调度方案

邹凤1，仲姣菲2，伍伟丽2，堵丁柱2，Lee Junghoon3

(1.达拉斯Real Time Resolutions公司,得克萨斯州达拉斯 75235,美国;
2.得州大学达拉斯分校计算机科学系,得克萨斯州达拉斯 75080,美国;
3.济州国立大学计算机科学与统计系,济州 690756，韩国)

收稿日期:2011-05-20 修回日期:2011-10-26 出版日期:2012-01-25 发布日期:2012-01-25

An Optimized RSU Scheduling Scheme for the Connectivity Problem in the HighlyPartitioned VANET

ZOU Feng1,ZHONG Jiaofei2,WU Weili2,DU Dingzhu2,Lee Junghoon3

(1.Real Time Resolutions Inc.,Dallas 75235,USA;
2.Department of Computer Science,University of Texas at Dallas,Dallas 75080,USA;
3.Department of Computer Science and Statistics,Jeju National University,Jeju 690756,Korea)

Received:2011-05-20 Revised:2011-10-26 Online:2012-01-25 Published:2012-01-25

摘要/Abstract

摘要：

车载自组网络VANET是一种拥有高度动态拓扑结构的移动自组网络。为了解决其频繁的网络分割问题，最新研究提出使用一种特殊的称为路侧单元RSU的基础设施部署于道路两侧来提高VANET连通性。本文主要研究RSU调度中的节能降耗问题：给定一组路侧单元，我们的目标是寻找指定时段内打开或关闭RSU的最优调度，以确保RSU系统所消耗的总能量最小化，同时维持VANET系统网络连通性。我们将这一问题分解为两个子问题，即网络瞬像调度问题和网络瞬像选取问题。网络瞬像调度问题用于决定某时刻VANET网络瞬像中所需的连通状态RSU的最小值，而网络瞬像选取问题则用于决定系统需要在哪些时刻更新网络瞬像。通过对这两个子问题的研究，我们最终给出关于RSU调度问题的完全解，并通过理论分析与实验结果证明本文的算法可以在保持VANET连通性的同时明显地节能降耗。

关键词: 车载自组网络, 路侧单元调度, 最优化, 节能降耗

Abstract:

Vehicle Adhoc Network (VANET) is a mobile adhoc network with the feature of highly dynamic topology. Recently, a special type of infrastructure called Roadside Unit (RSU) has been proposed to deal with the frequent network partitioning issue of VANET, which is deployed along the road to improve the VANET connectivity. In this paper, we mainly focus on how to save energy in the RSU scheduling problem. Our objective is to find the optimal scheduling to turn on or turn off the deployed RSUs within the system during a given time period, so that the overall energy consumption of these RSUs is minimized while the network connectivity is maintained. In order to solve this problem, we divide it into two subproblems, namely the snapshot scheduling problem and the snapshot selection problem. The former problem decides the minimum number of active RSUs required in a VANET snapshot at a given time point, while the latter problem decides the sequence of time points at which the snapshot must be updated. By solving these two subproblems, we present a complete solution to our RSU scheduling problem. Theoretical analysis and experimental results confirm the efficiency of our algorithms, which achieve significant improvement in energy saving while maintaining the VANET connectivity.

Key words: vehicle adhoc network;RSU scheduling;optimization;energy saving

邹凤1，仲姣菲2，伍伟丽2，堵丁柱2，Lee Junghoon3. 解决高度分割的车载自组网络连通性问题的路侧单元最优化调度方案[J]. J4, 2012, 34(1): 1-10.

ZOU Feng1,ZHONG Jiaofei2,WU Weili2,DU Dingzhu2,Lee Junghoon3. An Optimized RSU Scheduling Scheme for the Connectivity Problem in the HighlyPartitioned VANET[J]. J4, 2012, 34(1): 1-10.

参考文献［19］

［1］	Lochert C, Scheuermann B, Wewetzer C, et al. Data Aggregation and Roadside Unit Placement for a Vanet Traffic Information System［C］∥Proc of the Fifth ACM International Workshop on Vehicular InterNetworking, 2008:5865.
［2］	张瑾, 马良. Steiner最小树问题及其应用［J］.科学技术与工程, 2008, 8(15):42384257.
［3］	Zhang Y, Zhao J, Cao G. Service Scheduling of VehicleRoadside Data Access［J］. Mobile Networks and Applications, 2010,15(1):8396.
［4］	Bhm A, Jonsson M. Handover in IEEE 802.11pBased DelaySensitive VehicletoInfrastructure Communication［R］. Technical Report IDE0924, Halmstad University, 2009.
［5］	Garey M R, Johnson D S. Computers and Intractability:A Guide to the Theory of NPCompleteness［M］. New York, NY:W. H. Freeman & Co, 1990.
［6］	Berman P, Ramaiyer V. Improved Approximations for the Steiner Tree Problem［C］∥Proc of the Third Annual ACMSIAM Symposium on Discrete Algorithms, 1994:381408.
［7］	Hougardy S, Promel H J. A 1.598 Approximation Algorithm for the Steiner Problem in Graphs［C］∥Proc of the Tenth Annual ACMSIAM Symposium on Discrete Algorithms, 1999:448453.
［8］	Robins G, Zelikovsky A. Improved Steiner Tree Approximation in Graphs［C］∥Proc of the Eleventh Annual ACMSIAM Symposium on Discrete Algorithms, 2000:770779.
［9］	Chen D, Du DZ, Hu XD, et al. Approximations for Steiner Trees with Minimum Number of Steiner Points［J］. Journal of Global Optimization, 2000,18(1):1733.
［10］	Du DZ, Wang L, Xu B. The Euclidean Bottleneck Steiner Tree and Steiner Tree with Minimum Number of Steiner Points［C］∥Proc of the 7th Annual International Conference on Computing and Combinatorics, 2001:509518.
［11］	Lin GH, Xue G. Steiner Tree Problem with Minimum Number of Steiner Points and Bounded EdgeLength［J］. Information Processing Letters, 1999,69(2):5357.
［12］	Bettstetter C.Smooth Is Better Than Sharp:A Random Mobility Model for Simulation of Wireless Networks［C］∥Proc of the 4th ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems, 2001:1927.
［13］	Camp T, Boleng J, Davies V. A Survey of Mobility Models for Ad Hoc Network Research［J］. Wireless Communications and Mobile Computing (WCMC): Special Issue on Mobile Ad Hoc Networking: Research, Trends and Applications, 2002,2(5):483502.
［14］	Broch J, Maltz D A, Johnson D B, et al . A Performance Comparison of MultiHop Wireless Ad Hoc Network Routing Protocols［C］∥Proc of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking, 1998:8597.
［15］	Johnson D B, Maltz D A. Dynamic Source Routing in Ad Hoc Wireless Networks［M］∥Mobile Computing. Kluwer Academic Publishers,1996:153181.
［16］	Royer E M, Perkins C E. Multicast Operation of the AdHoc OnDemand Distance Vector Routing Protocol［C］∥Proc of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, 1999:207218.
［17］	Das S R, Perkins C E, Royer E E. Performance Comparison of Two OnDemand Routing Protocols for Ad Hoc Networks［C］∥Proc of INFOCOM’00, 2000:312.
［18］	Naumov V, Baumann R, Gross T. An Evaluation of InterVehicle Ad Hoc Networks Based on Realistic Vehicular Traces［C］∥Proc of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2006:108119.
［19］	Saha A K, Johnson D B. Modeling Mobility for Vehicular AdHoc Networks［C］∥Proc of the 1st ACM International Workshop on Vehicular Ad Hoc Networks, 2004:9192.

[1]	王扬, 陈智斌. 一种求解CVRP的动态图转换模型[J]. 计算机工程与科学, 2023, 45(05): 859-868.
[2]	张晶, 贺媛媛, . 融合正余弦优化与跳距优化的DV-Hop定位算法[J]. 计算机工程与科学, 2022, 44(04): 645-653.
[3]	王小平1，罗军1，沈昌祥2. 三边测量法的结果稳定性研究[J]. J4, 2012, 34(6): 12-17.
[4]	邢建英，李梦君，李舟军. 基于不变式生成的循环停机性验证[J]. J4, 2012, 34(4): 108-113.
[5]	周锦程1，王丹1，余泉1,2，张维1. 基于扩展SMO求解核函数非正定的SVR模型算法[J]. J4, 2012, 34(3): 122-127.
[6]	贾佳. 异构系统的异步应用级Checkpointing技术[J]. J4, 2011, 33(11): 54-59.
[7]	单美静曾振柄. 一个组合几何最优化未解决问题的半机械化解法[J]. J4, 2008, 30(11): 147-150.
[8]	陈丽戚飞虎. 基于梯度动力学的协同神经网络学习算法的改进[J]. J4, 2005, 27(1): 42-45.
[9]	胡小兵[1] 叶吉祥[2]. 定点距离最优化的遗传算法研究[J]. J4, 2003, 25(2): 5-6.
[10]	商临锋卢凯等. 并行文件系统中的最优化服务关系研究[J]. J4, 2001, 23(2): 87-89.

解决高度分割的车载自组网络连通性问题的路侧单元最优化调度方案

An Optimized RSU Scheduling Scheme for the Connectivity Problem in the HighlyPartitioned VANET

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献［19］

相关文章 10

编辑推荐

Metrics

本文评价

解决高度分割的车载自组网络连通性问题的路侧单元最优化调度方案

An Optimized RSU Scheduling Scheme for the Connectivity Problem in the HighlyPartitioned VANET

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 ［19］

相关文章 10

编辑推荐

Metrics

本文评价

参考文献［19］