清华大学交叉信息研究院

谈海生
方向: 算法,无线网络
职务: 博士后
Email:
地址: 北京清华大学信息科学技术(FIT)楼4-609
电话: (+86)-10-62795843-1612


English Version
教育背景

博士: 香港大学计算机系 (CS, HKU), (导师:Francis Chi-Moon Lau教授)

软件工程工学学士和工商管理理学学士(第二学位):中国科学技术大学 
(USTC)


研究方向

组合优化,计算复杂度,近似算法,分布式算法,无线传感器网络,认知无线电网络

论文
  • Channel Assignment in Cognitive Radio Networks

    • Complexity of Connectivity in Cognitive Radio Networks Through Spectrum Assignment *
      (with Hongyu Liang, Tiancheng Lou, Yuexuan Wang and Dongxiao Yu)
      the 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS'12), Ljubljana, Slovenia, LNCS 7718, pp. 108--119, 2013.
      [We firstly systematically studied the algorithmic complexity of connectivity in CRNs with multiple antennae through channel assignment. We considered the potential graphs are general graphs, complete graphs as well as trees.]
       
    • On the Complexity of Connectivity in Cognitive Radio Networks Through Spectrum Assignment *
      (with Hongyu Liang, Tiancheng Lou, Yuexuan Wang and Dongxiao Yu)
      In: Journal of Combinatorial Optimization (JOCO) [Accepted with minor revision], http://arxiv.org/abs/1301.0995.
      [An extended version of the paper above: besides more details provided, we also considered the special case where the potential graphs are of bounded treewidth.]

       
    • Computing Capacity and Connectivity in Cognitive Radio Ad-Hoc Networks
      (Qiang-Sheng Hua, Haisheng Tan, Yuexuan Wang, Hongxing Li, Dongxiao Yu, Francis C.M. Lau and Chuan Wu)
      the 12th International Symposium on Pervasive Systems, Algorithms, and Networks (I-SPAN'12), Texas, USA, 2012 [Invited Paper].
       
    • CAML: Channel Assignment for Multiply Links in Cognitive Radio Networks
      Manuscript.
       
    • Some Results on Rendezvous Problem
      Manuscript.
       
  • Interference Minimization in Wireless Ad-Hoc Networks

    • Minimizing Average Interference Through Topology Control
      (Tiancheng Lou, Haisheng Tan, Yuexuan Wang, and Francis C.M. Lau)
      the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS'11), September 8-9, 2011, Saarbruecken, Germany
      [We studied the interference minimization problem under the receiver-centric model.
      In 1D networks, we improved the time complexity to compute the minimum average interference (MAI) from O(n^6) to O(n^3).
      In 2D networks, we proved that the minimum maximum interference(MMI) could be bounded when minimizing the average interference.The bound is only determined by the node distances but not the network size n.
      We also proposed the first exact algorithm to compute the MAI in 2D networks.]

       
    • Average Interference Minimization Under the Protocol Model in Wireless Sensor Networks
      (Haisheng Tan, Tiancheng Lou, Yuexuan Wang, Yongcai Wang, and Francis C.M. Lau)
      Journal of Interconnection Networks (JOIN), 2013, to appear.
      [An extended version of the paper above: the results were extended from the receiver-centric model to the general protocol model.]
       
    • Minimizing Interference for the Highway Model in Wireless Ad-hoc and Sensor Networks
      (Haisheng Tan, Tiancheng Lou, Francis C.M. Lau, Yuexuan Wang,  and Shiteng Cheng)
      the 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'11), LNCS 6543, pp. 520-532, January 22-28, 2011, Novy Smokovec, Slovakia
      [We proposed the first polynomial-time exact algorithm to compute the MAI in 1D networks under the receiver-centric model.
      We proposed the first sub-exponential-time exact algorithm to compute the MMI in 1D networks under the receiver-centric model. ]

       
    • Exact algorithms to minimize interference in Wireless Sensor Networks
      (Haisheng Tan, Tiancheng Lou, Yuexuan Wang, Qiang-Sheng Hua, and Francis C.M. Lau)
      Theoretical Computer Science (TCS), Vol. 412, pp. 6913-6925, 2011.
      [An extended version of the paper above: the time complexity to compute the MAI was improved, and the procedures to construct the optimal topology through traceback were presented.]
       
    • A Tight Upper Bound of the Minimum Maximum Interference
      Manuscript.
       
  • Load Balance, Coverage, Link Scheduling and other Problems in Wireless Ad-Hoc Networks

    • Distributed Probabilistic Routing for Sensor Network Lifetime Optimization
      (Yongcai Wang, Haisheng Tan, Xiao Qi, Yuexuan Wang, Francis C.M. Lau, and Ruichuang Cao)
      Submitted to IEEE Transactions on Computers (TC).
      [An online network lifetime optimization algorithm was proposed through distributed probabilistic routing. Theoretical analysis and numerous simulations were presented to evaluate the optimality of the algorithm.]
       
    • Distributed Multiple-Message Broadcast in Wireless Ad-Hoc Networks under the SINR Model
      (Dongxiao Yu, Qiang-Sheng Hua, Yuexuan Wang, Haisheng Tan, and Francis C.M. Lau.)
      The 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO'12 ), June 30 - July 2, 2012, Iceland.
       
    • Distributed Multiple-Message Broadcast in Wireless Ad-Hoc Networks under the SINR Model
      (Dongxiao Yu, Qiang-Sheng Hua, Yuexuan Wang, Haisheng Tan, and Francis C.M. Lau.)
      Submitted to Theoretical Computer Science (TCS).
       
    • Maximizing Network Lifetime Online by a Localized Probabilistic Cost-Balancing Algorithm
      (Yongcai Wang, Yuexuan Wang, Haisheng Tan, and Francis C.M. Lau)
      the 10th International Conference on Ad Hoc Networks and Wireless (ADHOC-NOW'11), LNCS 6811, pp. 332-345, July 18-20, 2011, Paderborn, Germany
       
    • Minimum Latency Link Scheduling for Arbitrary Directed Acyclic Networks under Precedence and SINR Constraints
      (Qiang-Sheng Hua, Yuexuan Wang, Dongxiao Yu, and Haisheng Tan)
      Journal of Interconnection Network (JOIN), Vol. 12, Nos. 1 & 2: 85–107, 2011.
       
    • Arbitrary Obstacles Constrained Full Coverage in Wireless Sensor Networks
      (Haisheng Tan, Yuexuan Wang, Xiaohong Hao, Qiang-Sheng Hua, and Francis C.M. Lau)
      the 5th International Conference on Wireless Algorithms, Systems, and Applications (WASA'10), LNCS 6221, pp. 1-10, 2010,
      [We proposed an efficient full coverage method for a sensing region with arbitrary boundary and (opaque) obstacles based on the regular pattern deployment method, Delaunay triangulation and the 3-coloring algorithm.]
       
    • An Approximate Approach for Area Coverage in Wireless Sensor Networks
      (Haisheng Tan, Xiaohong Hao, Yuexuan Wang, Francis Lau, and Yuezhou Lv)
      To appera in ANT'13.
    • An Approximation Algorithm for the Path Coverage Problem
      Manuscript.
       
  • Others

    • A Generic Pigment Model for Digital Painting
      (Songhua Xu, Haisheng Tan, Xiantao Jiao, Francis C.M. Lau and Yunhe Pan)
      Computer Graphics Forum, Vol. 26(3), pp. 609 - 618, 2007. Editors: D. Cohen-Or and P. Slavk, Oxford, Blackwell Publishers.
    •  
    • A Generic Pigment Model for Digital Painting
      (Songhua Xu, Haisheng Tan, Xiantao Jiao, Francis C.M. Lau and Yunhe Pan)
      the 28th Annual Conference of the European Association for Computer Graphics (Eurographics): 609–618, September 2007, Prague, Czech Republic 
    • [We proposed a generic pigment model suitable for digital painting in a wide range of genres including traditional Chinese painting and water-based painting.
      Our approach is sorption and diffusion based, which offers a close resemblance to the true physical state of a real brush.]

       
           Note: Papers marked with * use alphabetic ordering of authors, following the convention of theoretical computer science.

获奖情况

  • CRCG Conference Grant, HKU, 2011

  • Postgraduate Scholarship, HKU, 2005 -- 2009

  • 安徽省优秀毕业生, 2004

  • 中国科学技术大学优秀毕业生,  2004

  • 郭沫若奖学金, USTC, 2003

  • 华为奖学金, USTC, 2002

  • 一等优秀学生奖学金, USTC, 2001

  • 保送生, USTC, 2000


会议及其他报告

  • "Connectivity and Discovery Problems in Cognitive Radio Networks: An Algorithmic Point of View", Shenzhen Institutes of Advanced Technology (SIAT), Shenzhen, China, Sept. 2012.

  • "Connectivity and Discovery Problems in Cognitive Radio Networks: An Algorithmic Point of View", Network Communications and Economics Lab, the Chinese University of Hong Kong (CUHK), Hong Kong, Sept. 2012.

  • "Complexity of Connectivity in Cognitive Radio Networks Through Spectrum Assignment", ALGOSENSORS'12, Ljubljana, Slovenia, Sept. 2012.

  • "Channel Assignment in Cognitive Radio Networks", Network Science Group, IIIS, Tsinghua University, China, Nov. 2011.

  • "Minimizing Average Interference Through Topology Control'', ALGOSENSORS'11, MPII, Germany, Sept. 2011.

  • "Minimizing Interference in Wireless Sensor Networks'', HP Labs, Beijing, China, Jun. 2011.

  • "Minimizing Interference for the Highway Model in Wireless Ad-hoc and Sensor Networks", SOFSEM'11, Nov\'{y} Smokovec, Slovakia, Jan. 2011.

  • "Arbitrary Obstacles Constrained Full Coverage in Wireless Sensor Networks", WASA'10, Beijing, China, Aug. 2010.