Based on the above analysis,if the deployment area is a cir- follows: cular region with the sink in the center,then due to the sym- m 2opt, metry of the topology,there must exist a consistent value for the parameter kopt to denote the boundary of the stor- maximize E[j·x, (8) age area.Then we enumerate all 2pt solutions for the i=1j=1 storage placement in the unit zone and maintain two tables: subject to E1..2pt and N1..2"pt.If we use the notion item to de- note a solution in a specified unit zone,then as compared to the all forwarding node solution,E[j](1<j<2kopt) N[·x,≤K =1= is used to hold the reduced energy for the jth item and Nj(1<j<2"P)is used to hold the essential number of 2kopti storages for the jth item.Hence the problem is formulated r,·0≤：for all1≤i≤m as follows: 0=1 Here ri;denotes the number of used copies of the jth kind of item in partition Pi.The objective is to maximize the overall reduced energy cost.The first constraint means that the overall number of storage nodes should be no more than kopt K.The second constraint means that,for each partition maximize Ej· (7) P,the overall number of items should be no more than 三1 which is the number of unit zones in Pi. subject to Obviously the above two unbounded multiple knapsack prob- 2kopt lems are all NP-hard.Therefore there exist no algorithms ∑N[j·x≤K to correctly solve the problem in polynomial-time.Hence i1 in the following part we propose algorithms to solve this problem in pseudo-polynomial time. 工50≤π 5.2 Dominance Relations Based on the formulations in the unbounded knapsack prob- lem,we observe that there exists such a property which can be called Dominance Relations:For a given item i in a spec- Here rj(1<j<kopt)denotes the number of used copies ified partition,suppose we could find another item j such that for the jth kind of item,which actually means the num- ber of unit zones applied with the jth solution for storage N[]≤N[ (9) placement.The objective is to maximize the overall reduced 1E≤E, energy cost.The first constraint means that the overall num- ber of storage nodes should be no more than K.The second and the above inequalities are satisfied with at least one less- than relationship.Then item i cannot appear in the optimal constraint means that the overall number of items should be solution,since we could always improve any potential solu- no more than,which is the number of unit zones.Hence the problem is reduced to the two-dimensional unbounded tion containing i by replacing i with j.Therefore we can knapsack problem:given the 2pt kinds of items.each with disregard the item i altogether.In such cases,item j is said a value ELi],a weight N[i]and a space 0,determine the to dominate i.Therefore,solving the unbounded knapsack problem can be made easier by throwing away items that number of each item to put into the knapsack,so that the total value is maximized and the total weight and space are will never be needed.Hence,we can sufficiently reduce the respectively less than or equal to a given limit,while the size of search space from 2to a certain level by leveraging the Dominance Relations. number of copies of each kind of item is not limited Furthermore,if the deployment area is in an irregular shape Therefore,in order to find the inherent dominance relations, we propose an algorithm as illustrated in Algorithm1.Ac- it can be divided into a certain number of fan-shaped par- titions.Suppose the number of the fan-shaped partitions cording to the algorithm,let n=2pt,the compute com- is m and each partition Pi has a degree of Bi(1 <i<m) plexities of the sorting and the following iterations are re- We first estimate the parameter kopt.;for each fan-shaped spectively O(n log n)and O(n),hence the overall compute complexity is O(n).In fact,due to the remove of the domi- partition Pi according to Eq.(6).For each partition Pi nated items in time,the number of iterations can be greatly we further divide it into a certain number of unit zones and enumerate all 2opt.solutions for the storage placement in reduced.Therefore,the average compute complexity can be the unit zone.Table Efi][1..2opt.]and N[i][1..2pt]are much less than O(n).Moreover,if the deployment area is divided into multiple partitions,the above algorithm needs maintained for each partition P.As compared to the all to find the dominance relations for each particular parti- forwarding node solution,Efi is used to hold the reduced tion Pi one by one,then the overall compute complexity is energy in partition Pi for the jth item,Nij is used to O(m.n2),here m is the number of partitions. hold the essential number of storages in partition Pi for the jth item.Then,similarly,the problem is reduced to an un- bounded multiple knapsack problem,which is formulated as 5.3 Dynamic Programming based AlgorithmBased on the above analysis, if the deployment area is a cir￾cular region with the sink in the center, then due to the sym￾metry of the topology, there must exist a consistent value for the parameter kopt to denote the boundary of the stor￾age area. Then we enumerate all 2kopt solutions for the storage placement in the unit zone and maintain two tables: E[1..2 kopt ] and N[1..2 kopt ]. If we use the notion item to de￾note a solution in a specified unit zone, then as compared to the all forwarding node solution, E[j](1 ≤ j ≤ 2 kopt ) is used to hold the reduced energy for the jth item and N[j](1 ≤ j ≤ 2 kopt ) is used to hold the essential number of storages for the jth item. Hence the problem is formulated as follows: maximize 2Xkopt j=1 E[j] · xj (7) subject to 2Xkopt i=1 N[j] · xj ≤ K 2Xkopt i=1 xj · θ ≤ π Here xj (1 ≤ j ≤ kopt) denotes the number of used copies for the jth kind of item, which actually means the num￾ber of unit zones applied with the jth solution for storage placement. The objective is to maximize the overall reduced energy cost. The first constraint means that the overall num￾ber of storage nodes should be no more than K. The second constraint means that the overall number of items should be no more than π θ , which is the number of unit zones. Hence the problem is reduced to the two-dimensional unbounded knapsack problem: given the 2kopt kinds of items, each with a value E[j], a weight N[j] and a space θ, determine the number of each item to put into the knapsack, so that the total value is maximized and the total weight and space are respectively less than or equal to a given limit, while the number of copies of each kind of item is not limited. Furthermore, if the deployment area is in an irregular shape, it can be divided into a certain number of fan-shaped par￾titions. Suppose the number of the fan-shaped partitions is m and each partition Pi has a degree of βi(1 ≤ i ≤ m). We first estimate the parameter kopt,i for each fan-shaped partition Pi according to Eq. (6). For each partition Pi, we further divide it into a certain number of unit zones and enumerate all 2kopt,i solutions for the storage placement in the unit zone. Table E[i][1..2 kopt,i ] and N[i][1..2 kopt,i ] are maintained for each partition Pi. As compared to the all forwarding node solution, E[i][j] is used to hold the reduced energy in partition Pi for the jth item, N[i][j] is used to hold the essential number of storages in partition Pi for the jth item. Then, similarly, the problem is reduced to an un￾bounded multiple knapsack problem, which is formulated as follows: maximizeXm i=1 2 kXopt,i j=1 E[i][j] · xi,j (8) subject to Xm i=1 2 kopt Xi i=1 N[i][j] · xi,j ≤ K 2 kopt Xi j=1 xi,j · θ ≤ βi for all 1 ≤ i ≤ m Here xi,j denotes the number of used copies of the jth kind of item in partition Pi. The objective is to maximize the overall reduced energy cost. The first constraint means that the overall number of storage nodes should be no more than K. The second constraint means that, for each partition Pi, the overall number of items should be no more than βi θ , which is the number of unit zones in Pi. Obviously the above two unbounded multiple knapsack prob￾lems are all NP-hard. Therefore there exist no algorithms to correctly solve the problem in polynomial-time. Hence in the following part we propose algorithms to solve this problem in pseudo-polynomial time. 5.2 Dominance Relations Based on the formulations in the unbounded knapsack prob￾lem, we observe that there exists such a property which can be called Dominance Relations: For a given item i in a spec￾ified partition, suppose we could find another item j such that  N[j] ≤ N[i], E[i] ≤ E[j], (9) and the above inequalities are satisfied with at least one less￾than relationship. Then item i cannot appear in the optimal solution, since we could always improve any potential solu￾tion containing i by replacing i with j. Therefore we can disregard the item i altogether. In such cases, item j is said to dominate i. Therefore, solving the unbounded knapsack problem can be made easier by throwing away items that will never be needed. Hence, we can sufficiently reduce the size of search space from 2kopt to a certain level by leveraging the Dominance Relations. Therefore, in order to find the inherent dominance relations, we propose an algorithm as illustrated in Algorithm1. Ac￾cording to the algorithm, let n = 2kopt , the compute com￾plexities of the sorting and the following iterations are re￾spectively O(n log n) and O(n 2 ), hence the overall compute complexity is O(n 2 ). In fact, due to the remove of the domi￾nated items in time, the number of iterations can be greatly reduced. Therefore, the average compute complexity can be much less than O(n 2 ). Moreover, if the deployment area is divided into multiple partitions, the above algorithm needs to find the dominance relations for each particular parti￾tion Pi one by one, then the overall compute complexity is O(m · n 2 ), here m is the number of partitions. 5.3 Dynamic Programming based Algorithm