电力通信网络边扩充二分算法

Bisection Algorithm of Edge Augmentation for Electrical Power Communication Network

随着智能电网的发展,电力通信系统自动交换光网络(ASON)的网架结构日趋复杂,拓扑优化方法成为保证可靠通信、提升网络健壮性的首要关键技术.为此,对电力通信ASON网络拓扑优化问题建模,并提出一种以代数连通度为测度的网络边扩充优化二分算法.通过理论证明赋权图的拉普拉斯矩阵对应特征方程式的单调性,进而采用二分算法快速求解该单调非线性特征方程式的根,确定最优边扩充策略.仿真结果表明在链路失效时,网络边扩充优化二分算法能够以O(4mn lb(???))低复杂度找到精确解,降低端到端通信路径长度,提升网络效能函数.

With the development of smart grid, the structure of electrical power communication automatic switched optical network （ASON） is getting increasingly complex. Topology optimization becomes one of the key technologies to guarantee the transmitting reliability as well as improve the robustness of network. In this paper, ASON＇s topology optimization problem was modeled and a bisection algorithm of edge augmentation for weighted network was proposed, in which the algebraic connectivity was defined as counting measure. The monotonicity of the characteristic equation corresponding to Laplace matrix for weighted graph was theoretically proved. Therefore, the bisection algorithm was employed to rapidly solve this monotone nonlinear characteristic equation and the optimal edge-expansion strategy was obtained. Simulation results show that when links fail, the bisection algorithm of edge augmentation can present exact solutions with low complexity of O （4ran lb （ξ/δ））, which can effectively reduce point-to-point communication path length and also improve the value of network＇s efficiency function.