上游充通大 SHANGHAI JIAO TONG UNIVERSITY A Distributed Algorithm to Construct Multicast Trees in WSNs: An Approximate Steiner Tree Approach Hongyu Gong,Lutian Zhao,Kainan Wang, Weijie Wu,Xinbing Wang Shanghai Jiao Tong University
Hongyu Gong, Lutian Zhao, Kainan Wang, Weijie Wu, Xinbing Wang Shanghai Jiao Tong University A Distributed Algorithm to Construct Multicast Trees in WSNs: An Approximate Steiner Tree Approach
Wireless Sensor Networks 上洋充通大学 SHANGHAI JIAO TONG UNIVERSITY Data dissemination and aggregation are common in wireless sensor networks Source/Sink Internet and satellite Monitoring Area Sensors Processing center 2
Wireless Sensor Networks 2 Data dissemination and aggregation are common in wireless sensor networks
What is multicast tree? 上浒充通大￥ SHANGHAI JIAO TONG UNIVERSITY ▣Connect a group of sensors ▣No redundant links 0 ▣Support one-to- many or many-to-one 0 data transmission 0 0 3
What is multicast tree? 3 Connect a group of sensors No redundant links Support one-tomany or many-to-one data transmission
Applications 上浒充通大学 SHANGHAI JIAO TONG UNIVERSITY : Traffic Smart home monitoring Safety Multicast tree Irrigation In WSN control Environmental Illumination monitoring control 4
Applications 4 Smart home Safety Environmental monitoring Illumination control Irrigation control Traffic monitoring Multicast tree In WSN
Communication Computation 上洋充通大学 SHANGHAI JIAO TONG UNIVERSITY Communication Min-length multicast tree MIMO FFT Computing
Communication & Computation
Evaluation of the multicast tree 上浒充通大￥ SHANGHAI JIAO TONG UNIVERSITY Euclidean tree length is an important concern Larger tree length might result in Higher probability of transmission failure:wireless interference More energy consumption:more power to transmit messages farther Longer delay:more time is needed for messages travel for a long distance 6
Evaluation of the multicast tree Euclidean tree length is an important concern Larger tree length might result in ✓ Higher probability of transmission failure: wireless interference ✓ More energy consumption: more power to transmit messages farther ✓ Longer delay: more time is needed for messages travel for a long distance 6
Outline 上浒充通大￥ SHANGHAI JIAO TONG UNIVERSITY Introduction and Challenges ▣Network Model Distributed algorithm Performance Evaluation Tree Length Running time Energy Consumption 7
Outline ❑ Introduction and Challenges ❑ Network Model ❑ Distributed algorithm ❑ Performance Evaluation ➢ Tree Length ➢ Running time ➢ Energy Consumption 7
Outline 上浒充通大学 SHANGHAI JIAO TONG UNIVERSITY Introduction and Challenges ▣Network Model Distributed algorithm QPerformance Evaluation Tree Length Running time >Energy Consumption 8
Outline ❑ Introduction and Challenges ❑ Network Model ❑ Distributed algorithm ❑ Performance Evaluation ➢ Tree Length ➢ Running time ➢ Energy Consumption 8
Our work 上浒充通大￥ SHANGHAI JIAO TONG UNIVERSITY An algorithm to construct the minimum-length tree in Wireless Sensor Networks In a distributed manner Time efficiency Energy efficiency 9
Our work ❑ An algorithm to construct the minimum-length tree in Wireless Sensor Networks ➢ In a distributed manner ➢ Time efficiency ➢ Energy efficiency 9
Challenge:relay selection 上游充通大警 SHANGHAI JIAO TONG UNIVERSITY Minimum-length tree is formulated as the Steiner Tree Problem,NP-hard in graph theory relay addition tree length decrease A 1 B 1 Fig.1 Without relay,tree length is 2 Fig.2 With relay,tree length is V3 10
Challenge: relay selection ❑ Minimum-length tree is formulated as the Steiner Tree Problem, NP-hard in graph theory relay addition tree length decrease 10 Fig. 1 Without relay, tree length is 2 Fig. 2 With relay, tree length is 3