برنامه نویسی شبکه چندپخشی متعدد حداقل هزینه با نرخ کوانتیده
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|70318||2013||11 صفحه PDF||سفارش دهید||8122 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Computer Networks, Volume 57, Issue 5, 7 April 2013, Pages 1113–1123
In this paper, we consider multiple multicast sessions with intra-session network coding where rates over all links are integer multiples of a basic rate. Although having quantized rates over communication links is quite common, conventional minimum cost network coding problem cannot generally result in quantized solutions. In this research, the problem of finding minimum cost transmission for multiple multicast sessions with network coding is addressed. It is assumed that the rate of coded packet injection at every link of each session takes quantized values. First, this problem is formulated as a mixed integer linear programming problem, and then it is proved that this problem is strongly NP-hard on general graphs. In order to obtain an exact solution for the problem, an effective and efficient scheme based on Benders decomposition is developed. Using this scheme the problem is decomposed into a master integer programming problem and several linear programming sub-problems. The efficiency of the proposed scheme is subsequently evaluated by numerical results on random networks.