当前位置:主页 > 新闻中心 > 学术活动预报 >

An Approximate Steiner Tree Approach

更新时间:2015-09-24 点击:
题目:
A Distributed Algorithm to Construct Multicast Trees in,WSNs: An Approximate Steiner Tree Approach
报告人:王新兵
时间:9月24日上午10:30-12:00
地点:新科技楼609会议室
摘要:
Multicast tree is a key structure for data dissemination from one source to multiple receivers in wireless networks. Minimum length multicast tree can be modeled as the Steiner Tree Problem, and is proven to be NP-hard. In this paper, we explore how to efficiently generate minimum length multicast trees in wireless sensor networks (WSNs), where only limited knowledge of network topology is available at each node. We design and analyze a simple and distributed algorithm, which we call Toward Source Tree (TST), to build multicast trees in WSNs. We show three metrics of TST algorithm, i.e., running time, tree length and energy effi- ciency. We prove that its running time is O( √ n log n), the best among all existing solutions to our best knowledge. We prove that TST tree length is in the same order as Steiner tree, give a theoretical upper bound and use simulations to show the ratio between them is only 1.114 when nodes are uniformly distributed. We evaluate energy efficiency in terms of the number of forwarding nodes in multicast trees, and prove that it is order-optimal. We give an efficient way to construct multicast tree in support of transmission of voluminous data.
 

 
王新兵:上海交通大学特聘教授,博士生导师。国家自然科学基金杰出青年基金获得者(2013),中国计算机学会青年科学家奖(2012),IEEE通信学会亚太区杰出青年研究者奖(IEEE ComSoc Asia-Pacific Outstanding Young Researcher Award 2009),IEEE通信学会亚太区杰出论文奖(IEEE ComSoc Asia-Pacific Outstanding Paper Award 2014),第12届霍英东基金获得者(2010),上海市浦江人才(2008),中国计算机协会YOCSEF上海分会首届IT新锐(2009)。
西电主页 回到首页 联系我们 西电导航 English Version
Copyright ©2005-2016 oice.xidian.edu.cn All rights reserved. 西安电子科技大学国际合作与交流处 版权所有
联系电话:029-8820 2220\4801\2221\2844 传真:029-88201620 电子邮箱:fao@xidian.edu.cn
地址:陕西省西安市太白南路2号 邮编:710071
电子工程学院网络信息中心设计维护seewebmaster@163.com