Optimal Transmission Topology Construction and Secure Linear Network Coding Design for Multicast with Integral Link Rates
Ruimin Zhao, Jin Wang, Kejie Lu, Xiangmao Chang, Lingzhi Li, Yanqin Zhu · 2016
Linear network coding (LNC) is a promising technology that can increase network throughput, improve transmission robustness and provide data confidentiality. In this paper, we investigate the optimal transmission topology construction and LNC design for secure multicast, i.e., the Integer Secure Multicast (ISM) problem. The ISM problem aims to find the transmission topology with integral link rates and design the secure LNC to (1) meet the requirements of weak security, (2) achieve the maximum secure transmission rate (STR) and (3) minimize transmission cost (TC) under the maximum STR guarantee. Specifically, in this paper, we firstly give theoretical analysis to show a sufficient and necessary condition that there exists a transmission topology with integral link rates and a secure LNC with STR R. Based on the sufficient and necessary condition, we then formulate the ISM problem into an integer linear programming (ILP) and also design an efficient transmission topology construction (TTC) algorithm to obtain a near-optimal solution of the problem. Based on Lagrangian relaxation and subgradient algorithm, the TTC algorithm is designed within polynomial computational complexity. Finally, we evaluate the performance of the proposed TTC algorithm together with a lower bound and an upper bound of the ISM problem through extensive experiments. Simulation results validate the effectiveness of the proposed TTC algorithm.