基于改进Dijkstra算法的配用电通信网流量调度策略

doi:10.11772/j.issn.1001-9081.2017112825

计算机应用 ›› 2018, Vol. 38 ›› Issue (6): 1715-1720.DOI: 10.11772/j.issn.1001-9081.2017112825

基于改进Dijkstra算法的配用电通信网流量调度策略

向敏, 陈诚

重庆邮电大学自动化学院, 重庆 400065

收稿日期:2017-12-01 修回日期:2018-02-13 出版日期:2018-06-10 发布日期:2018-06-13
通讯作者: 陈诚
作者简介:向敏(1974-),男,四川达州人,教授,博士,主要研究方向:智能电网、无线传感器网络、物联网;陈诚(1991-),女,湖北枝江人,硕士研究生,主要研究方向:智能电网、物联网。
基金资助:
重庆市重点产业共性关键技术创新专项重点研发项目（cstc2017zdcy-zdyfX0032）。

Traffic scheduling strategy based on improved Dijkstra algorithm for power distribution and utilization communication network

XIANG Min, CHEN Cheng

School of Automation, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

Received:2017-12-01 Revised:2018-02-13 Online:2018-06-10 Published:2018-06-13
Supported by:
This work is partially supported by the Key R&D Program of Common Key Technology Innovation for Key Industries in Chongqing (cstc2017zdcy-zdyfX0032).

摘要/Abstract

摘要： 针对配用电通信网中数据汇聚易产生拥塞的问题，提出了一种复合边权值流量调度路由算法。首先，依据跳数建立节点分层模型；然后，划分配用电业务优先级和节点拥塞等级；最后，以跳数、流量负载率和链路利用率为综合指标计算边权值，对需要流量调度的节点根据改进的Dijkstra算法进行路由选择，同时对重度拥塞节点按照配用电业务优先级进行调度。与最短路径（SPF）算法和贪婪背压算法（GBRA）相比，在数据生成率为80 kb/s时，所提算法紧急型业务丢包率分别减少了81.3%和67.7%，关键型业务丢包率分别减少了79%和63.8%。仿真结果表明，所提算法能有效缓解网络拥塞，提高网络有效吞吐量，降低网络端到端时延和高优先级业务的丢包率。

关键词: 电力通信网, 改进的Dijkstra算法, 流量调度, 复合边权值, 业务优先级

Abstract: Concerning the problem of being easy to generate congestion during data aggregation in power distribution and utilization communication network, a novel hybrid edge-weighted traffic scheduling and routing algorithm was proposed. Firstly, the hierarchical node model was established according to the number of hops. Then, the priorities of power distribution and utilization services and node congestion levels were divided. Finally, the edge weights were calculated based on the comprehensive index of hop number, traffic load rate and link utilization ratio. The nodes of traffic scheduling were needed for routing selection according to the improved Dijkstra algorithm, and the severe congestion nodes were also scheduled in accordance with the priorities of power distribution and utilization services. Compared with Shortest Path Fast (SPF) algorithm and Greedy Backpressure Routing Algorithm (GBRA), when the data generation rate is 80 kb/s, the packet loss rate of emergency service by using the proposed algorithm is reduced by 81.3% and 67.7% respectively, and the packet loss rate of key service is reduced by 79% and 63.8% respectively. The simulation results show that, the proposed algorithm can effectively alleviate network congestion, improve the effective throughput of network, reduce the end-to-end delay of network and the packet loss rate of high priority service.

Key words: power communication network, improved Dijkstra algorithm, traffic scheduling, composite edge weight, service priority

中图分类号:

TP393

向敏, 陈诚. 基于改进Dijkstra算法的配用电通信网流量调度策略[J]. 计算机应用, 2018, 38(6): 1715-1720.

XIANG Min, CHEN Cheng. Traffic scheduling strategy based on improved Dijkstra algorithm for power distribution and utilization communication network[J]. Journal of Computer Applications, 2018, 38(6): 1715-1720.

参考文献

[1] 雷煜卿,李建岐,侯宝素.面向智能电网的配用电通信网络研究[J].电网技术,2011,35(12):14-19.(LEI Y Q, LI J Q, HOU B S. Power distribution and utilization communication network for smart grid[J]. Power System Technology, 2011, 35(12):14-19.)
[2] KUZLU M, PIPATTANASOMPORN M, RAHMAN S. Communication network requirements for major smart grid applications in HAN, NAN and WAN[J]. Computer Networks, 2014, 67:74-88.
[3] ULUDAG S, LUI K S, REN W, et al. Secure and scalable data collection with time minimization in the smart grid[J]. IEEE Transactions on Smart Grid, 2016, 7(1):43-54.
[4] SHAO S, QIU X, MENG L. Smart gird distribution and consumption communication network architecture[J]. Journal of Communications, 2013, 8(8):480-489.
[5] JIANG T G. Power monitoring electronic/multimedia traffic scheduling in cognitive radio based smart grid[C]//Proceedings of the 2016 International Conference on Smart Grid and Clean Energy Technologies. Piscataway, NJ:IEEE, 2016:80-83.
[6] FAHEEM M, GUNGOR V C. Capacity and spectrum-aware communication framework for wireless sensor network-based smart grid applications[J]. Computer Standards & Interfaces, 2017, 53:48-58.
[7] 邵苏杰,郭少勇,邱雪松,等.基于加权队列的无线智能电网通信网采集数据流量调度算法[J].电子与信息学报,2014,36(5):1209-1214.(SHAO S J, GUO S Y, QIU X S, et al. Traffic scheduling algorithm based on weighted queue for meter data collection in wireless smart grid communication network[J]. Journal of Electronics & Information Technology, 2014, 36(5):1209-1214.)
[8] GHARAVI H, HU B. Multigate communication network for smart grid[J]. Proceedings of the IEEE, 2011, 99(6):1028-1045.
[9] HUANG J F, WANG H G, QIAN Y, et al. Priority-based traffic scheduling and utility optimization for cognitive radio communication infrastructure-based smart grid[J]. IEEE Transactions on Smart Grid, 2013, 4(1):78-86.
[10] YING L, SHAKKOTTAI S, REDDY A, et al. On combining shortest-path and back-pressure routing over multihop wireless networks[J]. IEEE/ACM Transactions on Networking, 2009, 19(3):841-854.
[11] GHARAVI H, XU C. Traffic scheduling technique for smart grid advanced metering applications[J]. IEEE Transactions on Communications, 2012, 60(6):1646-1658.
[12] SHAO S J, GUO S Y, QIU X S, et al. A random switching traffic scheduling algorithm in wireless smart grid communication network[C]//Proceedings of the 201423rd International Conference on Computer Communication and Networks. Piscataway, NJ:IEEE, 2014:1-6.
[13] HU B, GHARAVI H. Greedy backpressure routing for smart grid sensor networks[C]//Proceedings of the 2014 IEEE 11th Consumer Communications and Networking Conference. Piscataway, NJ:IEEE, 2014:32-37.
[14] 赵灿明,李祝红,闫凡,等.电力通信网络中负载均衡的路由协议[J].计算机应用,2016,36(11):3028-3032.(ZHAO C M, LI Z H, YAN F, et al. Load balanced routing protocol in electric power communication networks[J]. Journal of Computer applications, 2016, 36(11):3028-3032.)
[15] BASU A, LIN A, RAMANATHAN S. Routing using potentials:a dynamic traffic-aware routing algorithm[C]//Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. New York:ACM, 2003:37-48.
[16] 乔宏,张大方,谢鲲,等.分布式多网关无线mesh网公平协作路由算法[J].通信学报,2015,36(2):2015046-1-2015046-11.(QIAO H, ZHANG D F, XIE K, et al. Distributed fair cooperative routing in multi-gates wireless mesh network[J]. Journal on Communications, 2015, 36(2):2015046-1-2015046-11.)
[17] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1):269-271.
[18] 杨力,孙晶,潘成胜,等.基于多目标决策的LEO卫星网络多业务路由算法[J].通信学报,2016,37(10):25-32.(YANG L, SUN J, PAN C S, et al. LEO multi-service routing algorithm based on multi-objective decision making[J]. Journal on Communications, 2016, 37(10):25-32.)

基于改进Dijkstra算法的配用电通信网流量调度策略

Traffic scheduling strategy based on improved Dijkstra algorithm for power distribution and utilization communication network

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

[1]	李祝红, 赵灿明, 周方, 张信明. 电力通信网络中高效的OSPF流量负载均衡协议[J]. 计算机应用, 2017, 37(7): 1873-1876.
[2]	杨忠明, 梁本来, 秦勇, 蔡昭权. 多检测引擎监测的动态负载均衡算法[J]. 计算机应用, 2017, 37(3): 717-721.
[3]	赵灿明, 李祝红, 陶磊, 张信明. 基于故障传播模型与监督学习的电力通信网络故障定位[J]. 计算机应用, 2016, 36(4): 905-908.
[4]	赵灿明, 李祝红, 闫凡, 张信明. 电力通信网络中负载均衡的路由协议[J]. 计算机应用, 2016, 36(11): 3028-3032.