A Distributed Algorithm to Construct Multicast Trees in WSNs：An Approximate Steiner Tree Approach

上游充通大 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-to￾many 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