无线网路上使用扇形天线之最小电力单一来源多播绕送问题之快速最.PDFVIP

路 力 來 數* 立林 sheupr@.tw 論 論 路 力 來(The minimum-power single-source multicast problem with sectored antennas MPSSMSA ) MPSSMSA NP-complete力數 (Mixed Integer Linear Programming: MILP) formulation 來MPSSMSA MILP NP-complete路數 optimal MILP formulation 行 optimal MILP formulation 便 來 optimal MILP formulation 行度 來(1) 力(2)(3)preprocessing 論 兩 MPSSMSA optimal MILP formulations 便 MPSSMSA路力 MPSSMSA optimal MILP formulation 行度 力 MPSSMSA optimal MILP formulation 更 了 力 MPSSMSA optimal MILP formulation 行度 力路 *路 力量路 NSC 95-2221-E-224-014 1 Abstract In this paper, we address the minimum-power single-source multicast problem with sectored antennas (MPSSMSA). MPSSMSA is an NP-complete problem. An optimal mixed integer linear programming (MILP) formulation based on the direct power consumption model has been proposed to generate the optimal solution for MPSSMSA. However, MILP is also NP-complete itself. Therefore, the execution time of the optimal MILP formulation becomes very long when the number of nodes in a wireless network is large. Thus, the value of the optimal MILP formulation is limited. Three methods which can speed up the execution of an optimal MILP formulation have been developed recently. They are (1) using the incremental power consumption model, (2) using additional inequalities, and (3) using preprocessing techniques. In this paper, we attempt to adopt two of them to design a fast and optimal MILP formulation and an efficient preprocessing technique for MPSSMSA.