Challenge:quantitative analysis 上游充通大￥ SHANGHAI JIAO TONG UNIVERSITY Quantitative analysis of the Steiner Tree Famous Gilbert-Pollak conjecture on the Steiner ratio Prof.Dingzhu Du proved this conjecture Quantitative analysis in stochastic network Big-O notation of tree length is not so accurate Dingzhu Du > Consider the general distribution instead of the uniform distribution Hop count is not enough to describe the tree performance 11
Challenge: quantitative analysis Quantitative analysis of the Steiner Tree ➢ Famous Gilbert-Pollak conjecture on the Steiner ratio ➢ Prof. Dingzhu Du proved this conjecture ❑ Quantitative analysis in stochastic network ➢ Big-O notation of tree length is not so accurate ➢ Consider the general distribution instead of the uniform distribution ➢ Hop count is not enough to describe the tree performance 11 Dingzhu Du
Challenge:practical concern 上浒充通大学 SHANGHAI JIAO TONG UNIVERSITY ▣Time complexity Wireless sensor networks have dynamic topology,so the tree should be constructed in a short time. ▣Energy consumption Sensors are usually battery-powered,so the algorithm should be energy saving 12
Challenge: practical concern ❑ Time complexity Wireless sensor networks have dynamic topology, so the tree should be constructed in a short time. Energy consumption Sensors are usually battery-powered, so the algorithm should be energy saving. 12
Outline 上浒充通大学 SHANGHAI JIAO TONG UNIVERSITY Introduction and Challenges ▣Network Model Distributed algorithm QPerformance Evaluation Tree Length Running time >Energy Consumption 13
Outline ❑ Introduction and Challenges ❑ Network Model ❑ Distributed algorithm ❑ Performance Evaluation ➢ Tree Length ➢ Running time ➢ Energy Consumption 13
Network model 上游文通大￥ SHANGHAI JIAO TONG UNIVERSITY ▣ Sensor are identically and independently distributed in a unit square. A group of m members are randomly chosen to participate in multicasting among n nodes in the network. ▣ Density distribution of nodes is f(x),1<f(x)< E2,where x is the position vector,e1 and Ez are positive constants. The constructed tree is called Toward Source Tree (TST). 14
Network model ❑ Sensor are identically and independently distributed in a unit square. ❑ A group of m members are randomly chosen to participate in multicasting among n nodes in the network. ❑ Density distribution of nodes is f(x), 𝜖1 ≤ 𝑓(𝑥) ≤ 𝜖2 , where x is the position vector, 𝜖1 and 𝜖2 are positive constants. ❑ The constructed tree is called Toward Source Tree (TST). 14
Assumptions 上浒充通大粤 SHANGHAI JIAO TONG UNIVERSITY Every sensor knows its geographical location through GPS or signal sensing Every node is distinguished from each other by their identification numbers Only the source knows which nodes are chosen as destinations 15
Assumptions ❑ Every sensor knows its geographical location through GPS or signal sensing ❑ Every node is distinguished from each other by their identification numbers ❑ Only the source knows which nodes are chosen as destinations 15