基于多项式时间近似及其改进算法的WSN设计

赵海军 贺春林 王朝斌 蒲斌 陈毅红 崔梦天

引用本文:
Citation:

基于多项式时间近似及其改进算法的WSN设计

    通讯作者: 赵海军, zhaohai_jun@163.com
  • 中图分类号: TP393

WSN design based on polynomial time approximation and its improved algorithm

    Corresponding author: ZHAO Hai-jun, zhaohai_jun@163.com ;
  • CLC number: TP393

  • 摘要: 为了实现WSN设计中以满足一定的性能目标和网络成本的优化,提出了一种基于多项式时间近似及其改进算法. 首先将问题构建为一个多接收器网络-最小成本-跳数约束问题;然后将问题简化为一个加权集合覆盖问题的改进形式,从而采用加权集合覆盖贪婪算法来得到问题的解;其次,为了改进多项式时间近似算法得到的解,在前者的基础上采用启发式工作方式迭代地去除当前解的一部分,并通过试探搜索空间的其他部分来重建解,从而得到更高质量的解. 仿真实验结果表明,提出的算法在满足一定的QoS要求下,既能获得较低的设计成本,也能实现较少的执行时间.
  • 图 1  算法性能仿真流程框图

    Figure 1.  Flow diagram of algorithm performance simulation

    表 1  实验详细设置

    Table 1.  Experiments detail settings

    设置源数目潜在中继器潜在接收器位置区域/m2rmax/mhmax
    1203010无网格随机放置100×100205
    2405015无网格随机放置140×140205
    3305015采用网格随机放置140×140305
    下载: 导出CSV

    表 2  3种算法与基于LP的最优下界的成本性能比较

    Table 2.  Comparison of the cost performance of three kinds of algorithms against the optimal LP-based lower bound

    实验设置可用实例经验平均近似比 经验最坏近似比
    算法1算法2文献[13]算法算法1算法2文献[13]算法
    1471.351.291.26 2.882.882.72
    2321.111.051.01 1.361.211.06
    3601.091.011.00 1.831.251.08
    下载: 导出CSV

    表 3  3种算法与基于LP的最优下界的执行时间性能比较(s)

    Table 3.  Comparison of the running time performance of three kinds of algorithms against the optimal LP-based lower bound (s)

    实验设置算法1算法2文献[13]算法基于LP的最优下界
    平均最大平均最大平均最大平均最大
    1 1.15 2.72 3.46 15.1 258.6 673.4 37.4 138.1
    2 4.53 12.4 23.6 86.0 1 885.8 6 296.4 3 819 41 785
    3 5.17 11.5 12.1 34.9 311.5 638.2 489.0 5 395.3
    下载: 导出CSV
  • [1] 董辉, 杨录, 张艳花. 面向工业现场监测的无线传感器网络结构设计[J]. 仪表技术与传感器, 2017(2): 86-88. DOI:  10.3969/j.issn.1002-1841.2017.02.022. Dong H, Yang L, Zhang Y H. Design on wireless sensor network strusture for industrial field monitoring[J]. Instrument Technique and Sensor, 2017(2): 86-88.
    [2] 焦锏. 基于无线网络的环境监测系统设计[D]. 秦皇岛: 燕山大学, 2016.

    Jiao J. Design of environment monitoring system based on wireless network[D]. Qinhuangdao: Yanshan University, 2016.
    [3] 张燕, 朱海霞. 工业现场的远程监控系统设计[J]. 自动化技术与应用, 2017, 36(2): 119-122. Zhang Y, Zhu H X. Design of industrial environment remote monitoring system[J]. Techniques of Automation and Applications, 2017, 36(2): 119-122.
    [4] Bhattacharya A, Rao A, Naveen K P, et al. QoS constrained optimal sink and relay placement in planned wireless sensor networks[C]. Proceedings of 2014 International Conference on Signal Processing and Communications(SPCOM), Bangalore, India, 2014: 1-5
    [5] Bhattacharya A, Kumar A. An approximate inner bound to the QoS aware throughput region of a tree network under IEEE 802.15.4 CSMA/CA and application to wireless sensor network design[J]. Ad-HocNetworks, 2015, 33: 35-54.
    [6] 张浩, 刘兴, Gulliver T A, et al. 基于单基站天线阵列的超宽带定位AoA估计方法[J]. 电子与信息学报, 2013, 35(8): 2 024-2 028. Zhang H, Liu X, Gulliver T A, et al. AOA estimation for UWB positioning using a mono-station antenna array[J]. Journal of Electronics & Information Technology, 2013, 35(8): 2 024-2 028.
    [7] 周涛. 基于协作通信的无线传感器网络中继节点放置问题研究[D]. 合肥: 中国科学技术大学, 2013.

    Zhou T. Research on relay node placement in wireless sensor network via cooperative communication[D]. Hefei: University of Science and Technology of China, 2013.
    [8] GiacomelliI Cardoso D, NunesS DE M R E. Relay node placement in wireless sensor networks with bounded transmission range[C]. Proceedings of 2014 Brazilian Symposium on Computer Networks and Distributed Systems, Florianopolis, Brazil, 2014: 191-198.
    [9] Chelli A, Bagaa M, Djenouri D, et al. One-step approach for two-tiered constrained relay node placement in wireless sensor networks[J]. IEEE Wireless Communications Letters, 2016, 5(4): 448-45. DOI:  10.1109/LWC.2016.2583426.
    [10] Gupta S K, Kuila P, Jana P K. Genetic algorithm for k-connected relay node placement in wireless sensor networks[C]. Proceedings of the Second International Conference on Computer and Communication Technologies, Springer, New Delhi, India 2015, 379: 721-729.
    [11] Ma C, Liang W, Zheng M. Set Covering-based approximation algorithm for delay constrained relay node placement in wireless sensor networks[J]. Computer Science, 2015, 36(8): 1-5.
    [12] Ma C, Liang W, Zheng M. PSH: A pruning and substitution based heuristic algorithm for relay node placement in two-tiered wireless sensor networks[J]. Wireless Personal Communications, 2017, 94(3): 1 491-1 510. DOI:  10.1007/s11277-016-3694-x.
    [13] Sitanayah L, Brown K N, Sreenan C J. Planning the deployment of multiple sinks and relays in wireless sensor networks[J]. Journal of Heuristics, 2015, 21(2): 1-36.
    [14] Bhattacharya A, Kumar A. A shortest path tree based algorithm for relay placement in a wireless sensor network and its performance analysis[J]. Computer Networks, 2014, 71(2): 48-62.
    [15] Ahmed A A. An optimal complexity H. 264/AVC encoding for video streaming over next generation of wireless multimedia sensor networks[J]. Signal Image & Video Processing, 2016, 10(6): 1 143-1 150.
  • [1] 王海涛刘云 . 无线传感器网络中极大极小设置的分布式检测研究. 云南大学学报(自然科学版), 2014, 36(4): 497-503. doi: 10.7540/j.ynu.20130364
    [2] 周永录代红兵 . 无线传感器网络序列定位改进算法研究. 云南大学学报(自然科学版), 2013, 35(S2): 79-. doi: 10.7540/j.ynu.2013b34
    [3] 赵海军夏金红贺春林 . 基于多维标度和局部成本函数最小化的传感器节点定位算法. 云南大学学报(自然科学版), 2018, 40(4): 645-651. doi: 10.7540/j.ynu.20170554
    [4] 刘博赵东风丁洪伟李怀义 . 概率检测非坚持联合控制多通道无线传感器网络控制协议分析. 云南大学学报(自然科学版), 2010, 32(6): 639-645 .
    [5] 牛勤赵东风何敏 . 概率函数检测随机多址接入无线传感器网络MAC协议分析. 云南大学学报(自然科学版), 2011, 33(2): 136-140, .
    [6] 李怀义赵东风丁洪伟 . 双概率检测无线传感器网络MAC协议分析. 云南大学学报(自然科学版), 2010, 32(3): 280-287, .
    [7] 胡俊鹏沈济南梁芳 . 一种能耗均衡高效的无线传感器网络数据收集方案. 云南大学学报(自然科学版), 2015, 37(4): 500-504. doi: 10.7540/j.ynu.20140627
    [8] 刘海燕刘云 . 无线传感器网络中基于距离的簇头选择优化研究. 云南大学学报(自然科学版), 2014, 36(4): 490-496. doi: 10.7540/j.ynu.20130284
    [9] 韩格杨金华杨文静王云扬岳昆 . 一种面向无线传感器网络数据融合的路由联盟博弈方法. 云南大学学报(自然科学版), 2011, 33(5): 511-516,520.
    [10] 杨志军刘征丁洪伟毛磊张强 . 基于轮询控制的无线传感器网络MAC协议性能分析. 云南大学学报(自然科学版), 2020, 42(3): 437-443. doi: 10.7540/j.ynu.20190326
    [11] 李思明刘 云陈 熙 . 基于组模式在传感器调度部署中的优化. 云南大学学报(自然科学版), 2013, 35(4): 469-473. doi: 10.7540/j.ynu.20120472
    [12] 赵海军李敏崔梦天蒲斌李明东 . WDM-EPON中基于低成本保护结构的一种动态资源分配算法. 云南大学学报(自然科学版), 2012, 34(6): 658-663.
    [13] 唐菁敏王超 . 基于中继节点机制的分簇数据融合算法*. 云南大学学报(自然科学版), 2016, 38(5): 703-707. doi: 10.7540/j.ynu.20150785
    [14] 梁珺刘云 . 基于WSN分布式聚类均衡路由算法的优化研究. 云南大学学报(自然科学版), 2014, 36(6): 830-835. doi: 10.7540/j.ynu.20140056
    [15] 王灵矫梁雅媚郭华 . 基于距离估计的无线传感网络移动节点定位研究. 云南大学学报(自然科学版), 2019, 41(3): 476-483. doi: 10.7540/j.ynu.20180674
    [16] 周永录代红兵 . 基于RSSI的无线传感器网络定位算法研究. 云南大学学报(自然科学版), 2011, 33(S2): 202-205.
    [17] 周永录代红兵杨艳华 . 无线传感器网络动态概率接入MAC协议研究. 云南大学学报(自然科学版), 2014, 36(S2): 47-50. doi: 10.7540/j.ynu.2014a08
    [18] 唐菁敏马社方曹操张晓颍 . 基于数据压缩的无线传感器网络分簇路由算法. 云南大学学报(自然科学版), 2016, 38(1): 37-43. doi: 10.7540/j.ynu.20150181
    [19] 杨志军孙洋洋 . 无线传感器网络轮询控制系统研究. 云南大学学报(自然科学版), 2019, 41(1): 46-52. doi: 10.7540/j.ynu.20170671
    [20] 焦亚召刘云 . 应用信息论方法优化判定无线传感网络中最小传感器数目的研究. 云南大学学报(自然科学版), 2014, 36(5): 647-654. doi: 10.7540/j.ynu.20130553
  • 加载中
图(1)表(3)
计量
  • 文章访问数:  482
  • HTML全文浏览量:  198
  • PDF下载量:  13
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-11-11
  • 录用日期:  2020-03-02
  • 网络出版日期:  2020-04-23
  • 刊出日期:  2020-05-01

基于多项式时间近似及其改进算法的WSN设计

    通讯作者: 赵海军, zhaohai_jun@163.com
  • 1. 西华师范大学 计算机学院,四川 南充 637009
  • 2. 物联网感知与大数据分析南充市重点实验室,四川 南充 637009
  • 3. 西南民族大学 计算机科学与技术学院,四川 成都 610041

摘要: 为了实现WSN设计中以满足一定的性能目标和网络成本的优化,提出了一种基于多项式时间近似及其改进算法. 首先将问题构建为一个多接收器网络-最小成本-跳数约束问题;然后将问题简化为一个加权集合覆盖问题的改进形式,从而采用加权集合覆盖贪婪算法来得到问题的解;其次,为了改进多项式时间近似算法得到的解,在前者的基础上采用启发式工作方式迭代地去除当前解的一部分,并通过试探搜索空间的其他部分来重建解,从而得到更高质量的解. 仿真实验结果表明,提出的算法在满足一定的QoS要求下,既能获得较低的设计成本,也能实现较少的执行时间.

English Abstract

  • 工业监测和控制应用通常需要将大量的传感器分布在距控制中心数百米以外的地方. 传统上,传感器读数与控制中心的通信是通过有线网络,而有线网络的安装和维护比较麻烦,因此,用无线传感器网络(Wireless Sensor Network,WSN)代替有线网络成为必然[1-3].

    由于WSN的传感节点的通信范围小(一般只有几十米,依赖于环境的射频传播特性),通常需要多跳才能完成与控制中心的通信. 一方面需要从已经部署的这些静态传感器中收集测量数据,并封装成数据包,通常把这些静态传感器称为源;另一方面需要在已经部署的区域中放置额外的中继器和基站(Base Stations, BSs),以提供从每个源到至少1个BS的多跳路径. 源也可以作为来自其他源的数据包的中继. 这样获得的网络需要为在其上的数据包流量提供一定的服务质量(Quality-of-Service, QoS),如发送概率或数据包延迟. 而在大多数实际应用中,由于无线传播路径存在障碍物或禁止传播区域,所以不能在这种区域随意放置中继器和接收器,而只能在某些指定位置放置,这就导致了约束节点的放置问题,在这种问题中,节点被限制放置在某些潜在位置;此外,由于有些链路太长,可能导致高误比特率,从而导致大的数据包延迟.

    假设与每个接收器和中继器都有一个相关的成本,这种WSN的设计目标就是在潜在位置放置具有最小成本的接收器和中继器,并获得满足以下QoS目标的WSN:

    (1)存在一条从每个源节点到至少1个BS的路径;

    (2)任意路径上的最大延迟限制在一个给定的值dmax,且在任意路径上的数据包发送概率(在延迟范围内发送数据包的概率)≥pdel.

    在WSN中,实际链路质量事先是未知的,这是由于无线传播的随机模型,因此,基于这类模型的WSN设计不能保证在一个区域内部署时正常工作. “可用的”网络链路只能通过实地测量来确定,这就导致了基于模型设计的迭代算法是从部分部署开始,然后通过实地测量值来试探,从而更新有关现场链路质量,重复这种过程,直至获得满足实地QoS要求的设计为止. 这种迭代算法需要在每次迭代时调用一个网络设计子算法,以给定链路质量的网络图为输入,以满足QoS要求的子图为输出. 由于这种网络设计模块必须在每次迭代被调用,而且在最终设计之前可能会有若干次这样的迭代,希望这个模块具有较低的时间复杂度,因此,要寻求得到最优或接近最优解的快速算法. 文献[4-6]针对在指定位置仅有1个BS的特殊问题进行了研究,且文献[4-5]研究了端到端QoS目标的约束中继放置问题,但在给定位置只有单个基站,将QoS目标转换为在单包模型下每个源−接收器路径上的跳数约束,并提出了一种称为SPTiRP的近似算法;文献[7-9]研究了连通性和/或生存性无约束中继节点放置问题,其中必须将最小数量的中继器放置在二维区域来得到一棵树,生成给定的一组所需顶点(源和BS),但对QoS没作约束,证明了问题是NP-Hard的,并提出了一种近似算法;文献[10]研究了k连通性的最优中继放置(无约束)问题,对于任意固定的k≥1问题,提出了一种O(1)近似算法,但对QoS也没有施加任何约束;文献[11-12]研究了连通性和生存性约束中继放置问题. 尽管考虑了边缘长度的约束,但没包含路径约束,如沿途的跳数,因此,对端到端QoS没有任何约束,并分别提出了O(1)和O(lnn)近似算法;文献[13]研究了具有跳数约束的多接收器和中继器放置问题,但提出的是一种指数时间复杂度的局部搜索启发式算法. 尽管这种局部搜索启发式算法在实际中运行良好,但是算法的复杂度妨碍了在诸如智能连接的迭代网络设计过程中的使用.

    针对上述WSN设计中存在的某些不足,本文研究了更一般的问题,即在潜在位置可能部署多个接收器和中继器,以寻找一种算法,使其成本和运行时间性能接近最优. 这对WSN设计的可扩展性是很有用的.仿真实验结果表明,本文提出的算法能在满足一定的QoS要求下,获得较低的设计成本和较少的执行行时间.

    • 本文讨论来自于源节点流量很轻的情况下的问题. 通常,将“轻流量”定义为:对于任意链路(发送−接收机对)集,其传输相互干扰,在任何时刻网络中只有1条链路处于活跃状态(即携带数据包),称之为“单包流量模型”,这是符合实际的,如状态监测/工业遥测应用等[14]. 这时连续测量值之间的时间足够长,以致于测量值可错开以避免同时占用传输介质. 有关单包模型的适用性和合理性的详细讨论参见文献[5]. 下面来讨论在单包模型下如何将数据包级QoS目标映射到图级目标.

      给定一组源节点或要求的顶点Q、一组潜在中继位置R(每个位置的成本为cr),以及一组潜在接收位置B(每个位置的成本为cs),考虑一个图G=(V,E),V=QRBE由全部可用边构成.

      在整个研究过程中,假设全部节点都工作在相同的固定功率水平上,然后就可以通过对每个链路的数据包差错率(Packet Error Rate,PER)施加一个约束,或者通过约束允许的最大链路长度来定义可用边的集合E. 通过对图G中每个可用链路的链路质量进行分析[5],在每个源节点和接收器之间设置一个跳数界限hmax,就可以满足QoS目标(dmaxpdel). 考虑慢衰落链路的实际情况,以及由于随机信道差错引起的数据包丢失,因此,由于数据包重传,在每一跳存在随机时延,而且如果达到重传限制,则数据包可能被丢弃. 由于单包假设,则沿着路径的延迟是加性的,即延迟是沿途每一跳的延迟之和. 对于链路差错和随机衰落,以及无线物理层的参数和系统采用的介质访问控制(如IEEE 802.15.4 CSMA/CA的退避参数[15]),分析采用统计模型(可以从实地测量值得到).

    • 给定图G=(V,E),V=QRBE由全部可用边构成,每个接收器和中继器的成本分别为cscr,以及跳数约束为hmax,问题是从该图中提取一个最小成本(选择接收器和中继器的成本)生成Q的子图,使得每个源都有至少1个接收器的路径,其跳数≤hmax,将这个问题称之为多接收器网络-最小成本-跳数约束(MultiSink Network-Minimum Cost-Hop Constraint,MSN-MC-HC)问题. 在这个问题构建中,不考虑节点由于发送和接收而消耗的能量,因为在轻流量环境下,与节点的空闲时间相比,节点发送或接收数据包的时间部分很小.

    • 这部分针对MSN-MC-HC问题提出一种多项式时间近似算法及其改进算法—启发式算法. 算法首先将问题简化为加权集合覆盖问题的改进形式,然后采用加权集合覆盖贪婪算法来得到解. 由于加权集合覆盖贪婪算法是多项式时间的,故提出的算法是多项式时间的.

    • 步骤1 单个接收器、无中继器的情形:考虑图G仅对源Q和潜在接收器B的约束,对每个接收器b∈B,寻找根位于b的最短路径树(Shortest Path Tree,SPT)生成Q的源. 如果存在一个接收器b0使得根位于b0的SPT满足Q中每个源的跳数约束,则就完成了;最优解需要仅1个接收器,不需要中继器,否则进入下一步;

      步骤2 检验可行性:在图G(即现在包含全部源和中继器)上,得到一棵根位于每个潜在接收器位置的最短路径树,如果存在一个源,使其到全部接收器的最短路径长度超过hmax,则声明该问题不可行,否则进入下一步;

      步骤3 对于每个接收器biBi=1,…,|B|,识别源的集合即Qi,其到bi的最短路径长度≤hmax. 集合Qi$\subseteq$Q,就是说被bi所覆盖. 注意,步骤2中已确保了可行性 $ \cup _{i = 1}^{\left| B \right|}{Q_i} = Q$,还识别了中继器集合Ri$\subseteq $R,它到bi的最短路径长度≤hmax−1(这有助于降低步骤4的复杂度,实际上,Ri是中继器的集合,可以用来将Qi中的源连接到bi);

      步骤4 置j←0,用j作为迭代指标,置Q(0)i=QiB(0)=BB(j)表示迭代j开始时尚未选择的接收器的集合,Q(j)i表示迭代j开始时未被覆盖的源的集合,未被覆盖的源与一个BS biB(j)相关联;

    • 步骤5 对于每个ibiB(j),令G(j)iGQ(j)iRi∪{bi}的约束. 对G(j)i运行算法来得到中继器的一个近似最优子集 $\hat R_i^{(j)} \subseteq {R^i}$,它以≤hmax跳数将G(j)i中的源连接到bi

      步骤6 对于每个ibiB(j),考虑G(j)iQ(j)i$\hat R_i^{(j)}$bi的约束,用 $\hat G_i^{(j)}$ 表示这个图;

      步骤7 对于每个ibiB(j),定义 $\hat G_i^{(j)}$ 的成本为:

      $C_i^{(j)} = \frac{{{c_{\rm{s}}} + {c_{\rm{r}}} \times \left| {\hat R_i^{(j)}} \right|}}{{\left| {Q_i^{(j)}} \right|}}.$

      即把子图的成本计算作为每个源的总成本;

      步骤8 贪婪选择:在尚未选择的子图中选取成本最小的子图,即选取 ${\tilde G^{(j)}} = \arg {\min _{{{\tilde G}^{(j)}}}}C_i^{(j)}$

      步骤9 令 ${\tilde b^{(j)}}$ 为与 ${\tilde G^{(j)}}$ 相关联的接收器,${Q^{(j)}} = $$Q \cap {\tilde G^{(j)}}$${R^{(j)}} = R \cap {\tilde G^{(j)}}$. 如果 $ \cup _{k = 1}^j{Q^{(k)}} = Q$,则停止,即当全部源都被覆盖时停止. 否则进入下一步;

      步骤10 更新步骤:置 ${B^{(j + 1)}} = {B^{(j)}}\backslash {\tilde b^{(j)}}$. 对于每个ibiB(j+1),置 $Q_i^{(j + 1)} = Q_i^{(j)}\backslash ({\tilde G^{(j)}} \cap Q_i^{(j)})$. 此外,对于全部后续迭代,将R(j)中每个中继器的成本设置为零. 这样做的目的是使得由覆盖共享的源和中继器不会被计数超过1次;

      步骤11 置j←j+1,然后转到步骤5.

    • (1)如果最优解采用单个接收器而无中继器,则算法得到最优解(遵循步骤1);

      (2)对于接收器放置问题(即cr=0),算法完全简化为加权集合覆盖贪婪算法,从而得到接收器放置问题的最佳可能最坏情况近似保证(O(log(m))),其中m为源的数量,即|Q|=m

      (3)对于cs=0的子问题,最坏情况近似保证为m(hmax-1).

    • 已经知道,当最优解采用单个接收器而无中继器时,算法得到最优解,因此,需要关心的是任何最优解采用至少1个接收器和至少1个中继的器实例.

      引理1:假设 ${c_{\rm{s}}}/{c_{\rm{r}}} \geqslant \bar m(\bar m + 1)({h_{\max }} - 1)$,对于某些 $\bar m \in N$$m \succ \bar m \geqslant 1$,则下列结论成立:在算法的任何迭代中,如果大于 $\bar m$ 的源仍有待覆盖,则算法不能使覆盖最多 $\bar m$ 个剩余源的接收器优于覆盖全部剩余源的接收器,如果存在这样的接收器的话.

      证明:假设到迭代j(j≥1)的开始,m(j)个源已经被覆盖,且 $m - {m^{(j)}} \geqslant \bar m$,假设存在一个覆盖全部剩余源的接收器(尚未被选择),另一个接收器(尚未被选择)覆盖 $\bar m$ 个剩余的源,将这两个接收器分别表示为1和2,令 $n_1^{(j)}$$n_2^{(j)}$ 分别为接收器1和2在迭代j中算法选择的中继器的数量,则算法更有利于接收器2而不是接收器1当且仅当:

      $\begin{array}{*{20}{l}} {[{c_{\rm{s}}} + n_1^{(j)}{c_{\rm{r}}}]/[m - {m^{(j)}}] \succ [{c_{\rm{s}}} + n_2^{(j)}{c_{\rm{r}}}]/\bar m \Leftrightarrow }\\ {{c_{\rm{s}}}/{c_{\rm{r}}} \prec [\bar mn_1^{(j)} - (m - {m^{(j)}})n_2^{(j)}]/[m - {m^{(j)}} - \bar m]. }\\[-13pt] \end{array}$

      现在得到以下结果:

      (1) $n_1^{(j)} \leqslant (m - {m^{(j)}})({h_{\max }} - 1)$,因为每个剩余的源采用至多hmax跳数连接到接收器1;

      (2) $\dfrac{{\bar m(m - {m^{(j)}})}}{{m - {m^{(j)}} - \bar m}} = \dfrac{{\bar m}}{{1 - \bar m/(m - {m^{(j)}})}} \leqslant \bar m(\bar m + 1)$,这里由于 $m - {m^{(j)}} \geqslant \bar m + 1$,最后的不等式成立.

      则有:

      $\begin{array}{*{20}{l}} {\dfrac{{{c_{\rm{s}}}}}{{{c_{\rm{r}}}}} \geqslant \bar m(\bar m + 1)({h_{\max }} - 1) \geqslant \dfrac{{\bar m(m - {m^{(j)}})({h_{\max }} - 1)}}{{m - {m^{(j)}} - \bar m}}} \geqslant\\ {\qquad \dfrac{{\bar mn_1^{(j)}}}{{m - {m^{(j)}} - \bar m}} \geqslant \dfrac{{\bar mn_1^{(j)} - (m - {m^{(j)}})n_2^{(j)}}}{{m - {m^{(j)}} - \bar m}}.}\\[-20pt] \end{array}$

      类似如上所述地进行,并且注意到 $ f(\bar m) =$$ \bar m(\bar m + 1)$$\bar m$ 单调增加,可得到算法不利于接收器覆盖小于 $\bar m$ 个源的接收器1,这就完成了引理1的证明.

      利用引理1,可以得到算法最坏情况近似因子约束如下.

      定理1:考虑MSN-MC-HC问题的子问题,即存在仅采用1个接收器的可行解. 假设对于某些 $\bar m \in N$$m \succ \bar m \geqslant 1$${c_{\rm{s}}}/{c_{\rm{r}}} \geqslant \bar m(\bar m + 1)$,则以下结论成立:

      (1)由算法选择的接收器数量至多为 $\left\lceil {m/(\bar m + 1)} \right\rceil $

      (2)算法的最坏情况近似保证的上限为 $\varepsilon + m/\bar m$,其中ε∈[0,1),满足 $\left\lceil {m/(\bar m + 1)} \right\rceil = m/(\bar m + 1) + \varepsilon $.

      证明:

      (1)由于存在仅采用1个接收器的可行解,故全部m个源都可以以≤hmax跳数连接到该接收器. 因此,只要这个接收器在智能选择算法过程中不被选中,则引理1中的假设仍然成立,即存在一个能够覆盖全部剩余源的一个接收器;而且,一旦选择了这个接收器(如果有的话),算法就终止,因为全部源都被覆盖了. 因此,通过引理1,只要存在至少还有 $\bar m + 1$ 个源需要覆盖,算法就不能挑选覆盖至多 $\bar m$ 个源的任何接收器. 因此,算法在每次迭代中覆盖至少 $\bar m + 1$ 个源,直至剩余未覆盖的源的数量≤$\bar m$ 为止;最后,当未覆盖的源的数量≤$\bar m$ 时,就可以得到(根据引理1和 $\bar m(\bar m + 1)$ 的单调性)算法采用1个接收器覆盖这些剩余的源,故算法选择的接收器的数量至多为 $\left\lceil {m/(\bar m + 1)} \right\rceil $.

      (2)由于最优解采用至少1个接收器和至少1个中继器,因此最优成本至少为(cs+cr). 此外,智能选择算法所采用的中继数量的上界为m(hmax−1),因此采用1中的结果,最坏情况近似比(Approximation ratio,Ar)的上界为:

      $\begin{split} Ar \leqslant &\dfrac{{\left\lceil {m/(\bar m + 1)} \right\rceil {c_{\rm{s}}} + m({h_{\max }} - 1){c_{\rm{r}}}}}{{{c_{\rm{s}}} + {c_{\rm{r}}}}}=\\ & \dfrac{{(m/(\bar m + 1) + \varepsilon ){c_{\rm{s}}}/{c_{\rm{r}}} + m({h_{\max }} - 1)}}{{1 + {c_{\rm{s}}}/{c_{\rm{r}}}}} \leqslant\\ &{ \dfrac{{(m/(\bar m + 1) + \varepsilon ){c_{\rm{s}}}/{c_{\rm{r}}} + m({h_{\max }} - 1)}}{{{c_{\rm{s}}}/{c_{\rm{r}}}}}} =\\ &{ (m/(\bar m + 1) + \varepsilon ) + \dfrac{{m({h_{\max }} - 1)}}{{{c_{\rm{s}}}/{c_{\rm{r}}}}}}\leqslant\\ &{ (m/(\bar m + 1) + \varepsilon ) + m/\bar m(\bar m + 1)} = \varepsilon + m/\bar m, \end{split}$

      式中最后的不平等式成立是因为 ${c_{\rm{s}}}/{c_{\rm{r}}} \geqslant \bar m(\bar m + 1)$$({h_{\max }} - 1)$.

    • 为了改进上述多项式时间近似算法得到的解,我们提出一种多项式时间启发式算法. 启发式算法的工作方式是迭代地去除当前解的一部分,并通过试探搜索空间的其他部分来重建解. 算法实现步骤如下:

      步骤1 令N(0)为多项式时间近似算法得到的结果,N(0)是初始网络图G对源、选择接收器和选择中继器的约束. 置k=0,Nbest=N(0),解更新=false,令K为允许迭代的最大次数;

      步骤2 对于N(k)中的每个接收器bj,执行以下操作:

      ①试探接收器bj

      ②仅采用N(k)中的剩余接收器和全部潜在中继来运行多项式时间近似算法,以获得解N1

      如果N1是可行的,且N1的成本优于Nbest的成本,则置Nbest=N1,且解更新=true,否则,进入下一步;

      ③试探接收器bj,并采用G中全部剩余接收器和中继器运行多项式时间近似算法来获得解N2.

      如果N2是可行的,且N2的成本优于Nbest的成本,则置Nbest=N2,且解更新=true.

      步骤3 在对N(k)中的全部接收器进行试探后,如果解更新=true,则置k←k+1,N(k)=Nbest,并转到步骤2);

      步骤4 当解没有进一步更新的可能或迭代超过最大次数时停止.

      由于启发式算法的每次迭代采用多项式时间近似算法算法(它是多项式时间的),且由于迭代次数的上界为常数K,因此改进的启发式算法也是多项式时间的.

    • 由于MSN-MC-HC问题是NP-Hard的,通常计算最优解需要对潜在接收器和中继器的全部可能组合进行穷举搜索,这显然是不切实际的. 为此,我们通过求解MSN-MC-HC问题的ILP构建的LP松弛来得到问题实例的最优成本的下界作为比较基准.

      我们在3个不同的实验设置中将本文提出的2种算法和文献[13]提出的指数搜索启发式算法与基于ILP构建的LP得到的最优成本下界进行比较. 实验设置通过改变以下一个或多个参数获得:源数量、潜在中继器和潜在接收器数量、部署区域、通信范围、跳数约束和选择源节点位置和潜在节点位置. 在全部实验中,选取cs=10(单位成本),cr=1(单位成本) (这个选择满足定理1和定理2中关于cs/cr的假设)且 $\bar m = 1$.

      仿真中,考虑3个不同的正方形部署区域,部署区域划分为连续边长为10 m的方格, 并在每个方格中随机部署传感器节点, 数量从5到100,中继器节点从10到50. 对于设置下的每个实例,从这些格子点阵中随机选取源节点、潜在中继器位置和潜在接收器位置,实验详细设置如表1所示. 表中“采用网格随机放置”是指该区域被划分为边长为10 m的正方形单元格,表中“无网格随机放置”是指源位置、潜在中继器位置和潜在接收器位置的选取是按照区域上的连续均匀分布(不将区域划分为单元网格);其中的QoS链路带宽、发送器初始数据发和接受器初始数据接收由系统自动随机生成,每个节点在仿真时间内产生等量数据,数据有相同的长度,且每个节点的传输范围固定不变. 中继器数据转发采用可用于大型传感器网络的最小成本转发(Minimum Cost Forwarding,MCF)的多跳路由协议;实验仿真平台采用基于NS2的传感器网络仿真软件和Matlab R2011b,并结合C++在基于Linux的8GB RAM桌面上运行;仿真流程框图如图1所示.

      设置源数目潜在中继器潜在接收器位置区域/m2rmax/mhmax
      1203010无网格随机放置100×100205
      2405015无网格随机放置140×140205
      3305015采用网格随机放置140×140305

      表 1  实验详细设置

      Table 1.  Experiments detail settings

      图  1  算法性能仿真流程框图

      Figure 1.  Flow diagram of algorithm performance simulation

      为简单起见,将本文提出的多项式时间近似算法及其改进的启发式算法分别记为算法1和算法2. 对于每个设置中的每个实例,运行3种算法,并计算出该实例的基于ILP构建的LP得到的最优解下界,算法2中的最大迭代次数选取为25. 表2所示为3种算法与基于ILP构建的LP得到的最优解下界的成本性能比较. 对于每个设置的每个可行实例,我们计算出了3种算法关于基基于ILP构建的LP的下界的经验近似比即Ar=算法结果成本/LP解的下界成本,并把该设置实例中的这些值的最大值用作为该设置的经验最坏近似比;还计算出了算法的经验平均近似比. 令 $C_{{\rm{avg}}}^{({\rm{algo}})}$ 表示在一个设置下的可行实例算法结果的平均成本,${\bar C_{{\rm{LP}}}}$ 为这些可行实例的LP解的平均成本,然后计算出算法的经验平均近似比为 ${\bar \alpha _{{\rm{algo}}}} = C_{{\rm{avg}}}^{({\rm{algo}})}/{\bar C_{{\rm{LP}}}}$.

      实验设置可用实例经验平均近似比 经验最坏近似比
      算法1算法2文献[13]算法算法1算法2文献[13]算法
      1471.351.291.26 2.882.882.72
      2321.111.051.01 1.361.211.06
      3601.091.011.00 1.831.251.08

      表 2  3种算法与基于LP的最优下界的成本性能比较

      Table 2.  Comparison of the cost performance of three kinds of algorithms against the optimal LP-based lower bound

      表3中比较了3种算法的执行时间和基于ILP构建的LP的下界计算的运行时间.

      实验设置算法1算法2文献[13]算法基于LP的最优下界
      平均最大平均最大平均最大平均最大
      1 1.15 2.72 3.46 15.1 258.6 673.4 37.4 138.1
      2 4.53 12.4 23.6 86.0 1 885.8 6 296.4 3 819 41 785
      3 5.17 11.5 12.1 34.9 311.5 638.2 489.0 5 395.3

      表 3  3种算法与基于LP的最优下界的执行时间性能比较(s)

      Table 3.  Comparison of the running time performance of three kinds of algorithms against the optimal LP-based lower bound (s)

      表2表3可以看出:

      (1)在全部实验设置中,本文提出的算法1和算法2在成本方面的平均经验性能均在基于LP的最优成本下界的大约1.4倍以内,在最坏情况下,3种算法是基于LP的最优成本下界的约2.9倍,但实际性能会更好,因为这是仅与最优成本的下界进行的比较;

      (2)如所预期的,算法2的性能要优于算法1,尽管有稍高的运行时间成本;

      (3)算法1和算法2在运行时间上都比基于ILP构建的LP的下界的执行时间提高了1~2个数量级;

      (4)文献[13]的算法在成本方面比本文提出的算法1和算法2略好,但这种改进在运行时间上却付出了巨大的代价,在全部设置中,算法1和算法2比文献[13]的算法要快得多.

      算法1和算法2极快的执行时间是一个很有吸引力的选择,它们可用于现场交互迭代网络的设计.

      总之,与文献[13]的算法及基于ILP构建的LP的下界解相比,本文提出的算法2(以算法1为起点)在执行时间上获得了显著的改善,而在成本方面有很小的损失,这种极快的执行时间和微不足道的成本损失使得算法2成为用于迭代网络设计过程中的一个极好的选择.

    • 本文研究了确定最佳中继器和接收器节点放置策略的问题,以满足一定的性能目标如确保数据在一定最大延迟内传送到BS的跳数约束. 证明了这个问题是NP-Hard的,甚至很难在O(lnm)的因子范围内近似,其中m是源的数量;并针对这一问题,提出了一种多项式时间近似算法,算法简单、直观,在非常合理的时间内可以得到较好质量的解,同时还给出了算法最坏情况的性能;仿真实验结果表明,本文提出的算法在满足一定的QoS要求下,既能获得较低的设计成本,也能实现较少的执行时间.

参考文献 (15)

目录

    /

    返回文章
    返回