Tham khảo tài liệu 'wireless mesh networks 2010 part 4', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Access-Point Allocation Algorithms for Scalable Wireless Internet-Access Mesh Networks 49 - Input G V E a network topology with N APs N V hi the maximum number of hosts associated with the APi the i-th AP for i 1 N Sij the transmission speed of the ij-th link linkij from APi to APj in E X C V a set of GW candidates K the number of GW clusters H the limit on the number of associated hosts in a GW cluster bandwidth limit and P the limit on the number of APs in a GW cluster cluster size limit . - Output C Cj C2 Ck a set of GW clusters gk the GW in Ck for k 1 K and rp the communication route between APi and the GW. - Constraint to satisfy the following four constraints - the number of APs in any GW cluster must be P or smaller Ci P cluster size constraint - the number of associated hosts in any GW cluster must be H or smaller hj H jeCi bandwidth constraint - the APs must be connected with each other in any cluster connection constraint - one GW must be selected from GW candidates in X in any cluster GW constraint . - Objective to minimize the following cost function Fc Fc A max hop APi B max host linkij host linkkl 3 kleintf ij where A and B are constant coefficients the function max r returns the maximum value of x the function hop APi returns the number of hops or hop count between APi and its GW the function host linkij returns the number of hosts using linkij in the shortest route to the GW to represent the link load and the function intf ij returns the link indices that may occur the primary conflict with linkij. The A-term represents the maximum hop count and the B-term does the maximum total load of a link and its primarily conflicting links. The minimization of the A- and B-terms intends the maximization of the network performance. Proof of NP-completeness for AP clustering The NP-completeness of the decision version of the AP clustering problem AP clustering is proved through reduction from the NP-complete bin packing problem Bin packing Garey Johnson 1979
