The Minimal Communication Cost of Gathering Correlated .ppt

《The Minimal Communication Cost of Gathering Correlated .ppt》由会员分享，可在线阅读，更多相关《The Minimal Communication Cost of Gathering Correlated .ppt（16页珍藏版）》请在麦多课文档分享上搜索。

1、The Minimal Communication Cost of Gathering Correlated Data over Sensor Networks,EL 736 Final ProjectBo Zhang,Motivation: Correlated Data Gathering,Correlated data gathering core component of many applications, real life information processes Large scale sensor applications Scientific data collectio

2、n: Habitat Monitoring High redundancy data: temperature, humidity, vibration, rain, etc. Surveillance videos,Resource Constraint,Data collection at one or more sinks Network: Limited Resources Wireless Sensor Networks Energy constraint (limited battery) Communication cost computation cost Internet C

3、ost metrics: bandwidth, delay etc.,Problem:,What is the Minimum total cost (e.g. communication) to collect correlated data at single sink?,Model Formalization,Source Graph: GX Undirected graph G(V, E) Source nodes 1, 2, , N , sink t e=(i, j) E comm. link, weight we Discrete Sources: X= X1, X2, , XN

4、Arbitrary distribution p( X1=x1, X2=x2, , XN=xN ) Generate i.i.d. samples, arbitrary sample rate Task: collect source data with negligible loss at t,Model Formalization: continued,Linear costs g( Re, we ) = Re we , e ERe - data rate on edge e, in bits/sample we - weight depends on applicationFor com

5、munication cost of wireless linkswe l , 2 4 , l Euclidean distanceGoal: Minimize total Cost,Minimal Communication Cost -Uncapacitated and data correlation ignored,Sink-t,1,2,3,4,5,6,8,9,11,12,7,10,Link-Path Formulation ECMP Shortest-Path Routing: Uncapacitated Minimum Costindices d = 1, 2, .,D deman

6、ds p = 1, 2, ., Pd paths for demand d e = 1, 2, .,E linksconstants hd volume of demand d edp = 1 if link e belongs to path p realizing demand d variables We metric of link e, w = (w1, w2, .,wE) Xdp(w) (non-negative) flow induced by link metric system w for demand d on path pminimize F = e Wed pedp X

7、dp(w)constraints p Xdp(w) = hd, d= 1, 2, .,D,Data correlation Tradeoffs: path length vs. data rate,Routing vs. Coding (Compression) Shorter path or fewer bits? Example: Two sources X1 X2 Three relaying nodes 1, 2, 3 R - data rate in bits/sample Joint compression reduces redundancy,Data correlation -

8、 Previous Work,Explicit Entropy Encoding (EEC) Joint encoding possible only with side info H(X1,X2,X3)= H(X1)+ H(X2|X1)+ H(X3|X1,X2) Coding depends on routing structure Routing - Spanning Tree (ST) Finding optimal ST NP-hard,X2,X3,H(X1),H(X2),Sink-t,1,2,3,4,5,6,7,8,9,10,11,12,X1,H(X1,X2, X3),Data co

9、rrelation - Previous Work (Contd),Slepian-Wolf Coding (SWC): Optimal SWC scheme routes? Shortest path routing rates? LP formulation (Cristecu et al, INFOCOM04),Sink-t,1,2,3,4,5,6,8,9,11,12,Correlation Factor,For each node in the Graph G (V,E), find correlation factors with its neighbors. Correlation

10、 factor uv , representing the correlation between node u and v. uv = 1 r / RR - data rate before jointly compressionr - data rate after jointly compression,Correlation Factor (Contd),Shortest Path Tree (SPT):Total Cost: 4R+r Jointly Compression:Total Cost: 3R+3rAs long as = 1- r/R 1/2, the SPT is no

11、 longer optimal,All edge weights are 1,Minimal Communication Cost local data correlation ：Add Heuristic Algorithm,Step 0: Initially collecting data at sink t via shortest path. Compute Cost Fi(0) = e Ri We, where We is the weight of link e realizing demand Ri. Set Si(0) = j, where j is the next-hop

12、of node i. i, j = 1, 2 N, i j . Set iteration count to k = 0. Let Mi denote the neighbors of node i. Step 1: For j MiSi(k), doFij(k+1) = Fi(k) RiWij+RiWij + e (Ri ij) We Step 2: Determine a new j such thatFij(k+1) = min Fij(k+1) Fi(k).If there is no such j, go to step 4.Step 3: UpdateSi(k+1) = j Set

13、 Fi(k+1) = Fij(k+1) and k := k + 1 and go to Step 1.Step 4: No more improvement possible; stop.,Add Heuristic: example,First Step: Shortest path routing,Sink-t,1,2,3,4,5,6,9,10,12,7,11,8,After Heuristic: When ij 1/2, j will be the next hop of i.,Local data correlation: analysis,Information from neighbors needed Optimal? Approximation algorithm Other factors took into account: energy, capacity,Thanks!,