Hence from the above formula we obtain: And from steps of Algorithm 1,we can deduce the recursive x·W formation of calculating aj.k,there exists: =P+-市 i·W 台V-2+(y- ai.k W∑1.k-1 (9) /”11.k-1(1-工P+∑-1a4,k-1-(1-】严 (15) Therefore according to formula 9,we define aj(,y)as 0j,0= dj.o follows: Based on the above recursive relationship between aj.and a(x,y）= W jk+1 it is sufficient to prove limk=1.due (10) 1, V(工-x2+(y-P to space constraints of this paper,we omit the detail proof procedure here. ■ Through replacing the counterpart in formula 9 with j(,y). we have: B.Algorithm Algorithm I Iterative Approximation of the Optimal Solu- ∑a(c,)=∑·a,) tion i=1 j=1 Step 1.First calculate the gravity point (G,yG)of the object set O,which is actually the optimal solution for the We extract z from the left part of the equation,then we get: problem of E=oo(si,Oj).Wj,thus we have: aj(r,y) E=4色功 W =∑=1（元 w小·x防 =∑=1(w) (16) And we further define Bi(r,y)as follows: We set it as the initial solution,so we have T0=TG ai(x,y) 6(x,）= ∑1a(c,刃 (11) o=yG Step 2.Execute the iteration procedure: Hence we have: k+1=86,职：西 (17) 1k+1=∑5=1k,)·劝 月（） Siep3.Check that if|k+-s|≤eand|+-业|≤e(e j=1 is a constant and 0<<1).if so,we will stop the iteration Similarly,we have the following equation to calculate y: and go to Step 4,else k =k+1,go to Step 2. 2 Step 4.Set k+1as the final approximate solu- y=∑，)·劝 y*=张+1 tion. j=1 Here in Step I we utilize the gravity point(xG,UG)as the Thus we finally have the following recursive equations: initial solution,the motivation is to make the convergence x=n procedure have fewer iteration rounds compared with the {苏张副 (12)random selection strategy for initial solution,it is actually not a necessary premise for the iterative algorithm. Therefore we can calculate the optimal solution (,y) V.LOAD BALANCE SCHEME FOR STORAGE PLACEMENT through iteration based on equations 12.We will illustrate the iteration steps in detail with Algorithm 1,but before that,we A.Principle prove the convergence of this iteration procedure. Theorem linThe iteration result of Storage xk+1=】 will converge to the optimal solution (,) Proof:We define the Euclidean distance from storage point S to object O;after the kth iteration as di.k,thus to prove the theorem,we just need to prove: Node Node lim dj.k+1=1 (13) k-∞di.k Fig.2.Communication Paradigm of Storage Nodes From formula 10,we getthus we only have to prove: Analyzing on the model proposed in Section 3,note that each storage node will receive event messages from event lim a1,k+1=1 (14) k→0∞0j,k nodes and query messages from query nodes,and will send 978-1-4244-2324-8/08/S25.00©2008EEE. 3 This full text paper,B9dise4vgfE毛rfei98sO6P9件形69s代hlim艳E头6r裙sfl8P”2008 proceedings.Hence from the above formula we obtain: n j=1 x · Wj (x − xj )2 + (y − yj )2 = n j=1 xj · Wj (x − xj )2 + (y − yj )2 (9) Therefore according to formula 9, we define αj (x, y) as follows: αj (x, y) = Wj (x − xj )2 + (y − yj )2 (10) Through replacing the counterpart in formula 9 with αj (x, y), we have: n j=1 x · αj (x, y) = n j=1 xj · αj (x, y) We extract x from the left part of the equation, then we get: x = n j=1 αj (x, y) n j=1 αj (x, y) · xj And we further define βi(x, y) as follows: βj (x, y) = αj (x, y) n j=1 αj (x, y) (11) Hence we have: x = n j=1 βj (x, y) · xj Similarly, we have the following equation to calculate y: y = n j=1 βj (x, y) · yj Thus we finally have the following recursive equations: x = n j=1 βj (x, y) · xj y = n j=1 βj (x, y) · yj (12) Therefore we can calculate the optimal solution (x∗ i , y∗ i ) through iteration based on equations 12. We will illustrate the iteration steps in detail with Algorithm 1, but before that, we prove the convergence of this iteration procedure. Theorem 1: The iteration result of xk+1 = n j=1 β(xk, yk) · xj yk+1 = n j=1 β(xk, yk) · yj will converge to the optimal solution (x∗ i , y∗ i ). Proof: We define the Euclidean distance from storage point S to object Oj after the kth iteration as dj,k, thus to prove the theorem, we just need to prove: lim k→∞ dj,k+1 dj,k = 1 (13) From formula 10, we get αj,k(x, y) = Wj dj,k , thus we only have to prove: lim k→∞ αj,k+1 αj,k = 1 (14) And from steps of Algorithm 1, we can deduce the recursive formation of calculating αj,k, there exists: ⎧ ⎨ ⎩ αj,k = Wj · n √ l=1 αl,k−1 [ n l=1 αl,k−1·(xl−xj )]2+[ n l=1 αl,k−1·(yl−yj )]2 αj,0 = Wj dj,0 (15) Based on the above recursive relationship between αj,k and αj,k+1, it is sufficient to prove limk→∞ αj,k+1 αj,k = 1, due to space constraints of this paper, we omit the detail proof procedure here. B. Algorithm Algorithm 1 Iterative Approximation of the Optimal Solu￾tion Step 1. First calculate the gravity point (xG, yG) of the object set O, which is actually the optimal solution for the problem of Ei = Oj∈O d2(si, Oj ) · Wj , thus we have:  xG = n j=1 ( Wj n j=1 Wj ) · xj yG = n j=1 ( Wj n j=1 Wj ) · yj (16) We set it as the initial solution, so we have x0 = xG y0 = yG . Step 2. Execute the iteration procedure: xk+1 = n j=1 β(xk, yk) · xj yk+1 = n j=1 β(xk, yk) · yj (17) Step 3. Check that if | xk+1−xk xk | ≤ ε and | yk+1−yk yk | ≤ ε (ε is a constant and 0 <ε< 1), if so, we will stop the iteration and go to Step 4, else k = k + 1, go to Step 2. Step 4. Set x∗ = xk+1 y∗ = yk+1 as the final approximate solu￾tion. Here in Step 1 we utilize the gravity point (xG, yG) as the initial solution, the motivation is to make the convergence procedure have fewer iteration rounds compared with the random selection strategy for initial solution, it is actually not a necessary premise for the iterative algorithm. V. LOAD BALANCE SCHEME FOR STORAGE PLACEMENT A. Principle Fig. 2. Communication Paradigm of Storage Nodes Analyzing on the model proposed in Section 3, note that each storage node will receive event messages from event nodes and query messages from query nodes, and will send This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE "GLOBECOM" 2008 proceedings. 978-1-4244-2324-8/08/$25.00 © 2008 IEEE. 3 Authorized licensed use limited to: Nanjing University. Downloaded on July 11,2010 at 07:40:16 UTC from IEEE Xplore. Restrictions apply.