GU Yu, JI Yusheng, CHEN Hongyang, ZHAO Baohua. Using Mobile Sinks in WSN: Computational Complexity and a Theoretical Bound[J]. Chinese Journal of Electronics, 2011, 20(1): 147-150.
Citation: GU Yu, JI Yusheng, CHEN Hongyang, ZHAO Baohua. Using Mobile Sinks in WSN: Computational Complexity and a Theoretical Bound[J]. Chinese Journal of Electronics, 2011, 20(1): 147-150.

Using Mobile Sinks in WSN: Computational Complexity and a Theoretical Bound

  • Received Date: 2009-11-01
  • Rev Recd Date: 2010-01-01
  • Publish Date: 2011-01-05
  • In this paper, we study the lifetime optimization problem in wireless sensor networks using mobile sink nodes. This problem is inherently difficult since we need to consider both sink scheduling and data routing. Through a simple case study we develop a novel notation named the Placement pattern (PP) to bound traffic patterns with candidate locations. This significantly decreases the number of elements needed to be scheduled. Based on the PP, we mathematically formulate this optimization problem as a Mixed-integer non-linear programming (MINLP), which is very tough and time consuming to solve. By proving that the problem is NP-complete, we point out that instead of seeking an optimal algorithm, heuristic algorithms, especially those with performance guarantee, would be much more desirable to develop. Furthermore, in order to help identify performance gains of heuristic algorithms proposed in the future, we develop a Linear programming (LP) formulation which serves as an upper bound by adopting a reformulation and relaxation technique.
  • loading
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (588) PDF downloads(654) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return