论文部分内容阅读
摘要： 针对在三维空间中，对于中继节点（RN）的位置受限并且是双层拓扑的情况，提出了一种基于混合整数线性规划的中继节点放置算法，该算法首先考虑三维空间中继节点放置的物理层模型，然后基于混合整数线性规划（MIPS）给出最优能效的分簇，使得每个传感器节点与相应簇头之间的传输距离最小.仿真结果表明：与只考虑最小化簇内距离的中继节点放置算法相比，本算法在降低重传率和延长网络生命周期方面都有较大的改善.
关键词：
中继节点； 无线传感器网络； 双层受限； 整数线性规划
中图分类号： TN 929.5文献标志码： A文章编号： 10005137（2018）02022005
Research on the placement algorithm of twotiered constrained
relay nodes in wireless sensor networks
Xiang Haokai， Zhou Xiaoping*， Wang Jianan， Li Li， Huang Jiahui
（The College of Information，Mechanical and Electrical Engineering，Shanghai Normal University，Shanghai 200234，China）
Abstract：
In threedimensional space，when the location of relay nodes is limited and it is a twolayer topology，a relay location algorithm based on mixed integer linear programming （MILP） is proposed.The algorithm first considers the physical layer model placed by relay nodes in threedimensional space.Then，the optimal energy efficient clustering is given based on mixed integer linear programming.So that the transmission distance between each sensor node and its corresponding cluster head is the minimized.The simulation results show that compared with the traditional relay node algorithm that only considers the minimum intra cluster distance，the algorithm has a great improvement in reducing the retransmission rate and prolonging the life cycle of the network.
Key words：
relay node； wireless sensor networks； twotiered constrained； mixed integer linear programming
收稿日期： 20171227
基金項目： 上海市自然科学基金项目（16ZR1424500）
作者简介： 向浩凯（1993-），男，硕士研究生，主要从事无线传感器网络方面的研究.Email：2283557476@qq.com
导师简介： 周小平（1981-），男，博士，副教授，主要从事宽带无线通信、新一代移动通信和物联网技术方面的研究.Email：zxpshnu@163.com
*通信作者
引用格式： 向浩凯，周小平，王家南，等.无线传感器网络中双层受限中继节点放置算法研究 [J].上海师范大学学报（自然科学版），2018，47（2）：220-224.
Citation format： Xiang H K，Zhou X P，Wang J N，et al.Research on the placement algorithm of twotiered constrained relay nodes in Wireless Sensor Networks [J].Journal of Shanghai Normal University （Natural Sciences），2018，47（2）：220-224.
0引言
网络节点的合理布局是无线传感器（WSN）网络运行的首要前提.在WSN的大多数应用场景中，传感器节点（SN）和网关节点（GN）的布局位置相对固定，并且它们的能量往往难以补充，为了延长网络生命周期，提升网络连通性与可靠性，可以通过放置中继节点（RN）的方式来实现[1].因此，中继节点布局的优劣往往决定了无线传感器网络的生命周期、通信质量[2].
RN的布局分为单层网络结构（singletiered）和双层网络结构（twotiered）两种[3].在单层网络结构中，SN和RN都需要转发数据，而在双层网络结构中，SN只需要将自身采集的数据传送给RN，不需要转发其他传感器节点的数据.文献[4]对于单层网络结构的情况，将最少放置RN的问题转化成一个Steiner树的问题，解出最小化的Steiner点数和边长，便可得到最小放置RN的个数和位置.文献[5]对于文献[4]中的RN放置位置不受限的问题进行改进，中继节点只能放置在预先设定的位置上，给出了基于多项式时间复杂度的近似算法. 文獻[6]提出了一步受限RN放置算法，保证SN与基站相连接的情况下放置最小数量的中继节点.针对文献[6]没有考虑网络的容错性能，文献[7]和[8]在满足网络容错需求的情况下，基于Steiner树的理论给出最小数量放置RN的探索式算法.
上述文献主要基于簇内距离最小化来实现RN的最优化放置，没有将物理因素的影响考虑在内.本文作者考虑在三维空间中，物理层参数（信道衰落和信噪比）对RN放置的影响，给出基于瑞利衰落的现实物理层模型；同时，基于混合整数线性规划（MIPS），得到SN与其簇头之间传输距离的最小值，从而在满足通信要求的前提下，得到RN的最优化放置位置.
1系统模型
本研究场景的系统模型如图1所示，其中RN作为簇头，负责收集来自SN的数据并将其转发到基站，对于此问题，需要找到最优化的RN部署方案，使每一个传感器都与基站连接.
基站与基站之间是通过有线的方式连接的，u代表发射节点，v代表接收节点，发射功率分别为Pu和Pv，两个节点之间的信道增益为au，v，瑞利块衰落在同一个块中信道增益保持常量.在本系统中，考虑了其他节点对节点v的干扰，节点w对节点v的衰减系数为aw，v，服从瑞利分布.从节点v所获得的接收信号
2双层受限RN放置算法
为了能够最优化放置RN，减少所提方案的复杂度，假设节点u的发射范围为ρu，它的大小由节点发射功率决定，也就是说当节点v与节点u之间的距离不超过ρu，那么节点u就能把节点v选作为父节点.
由（4），（5）式可知，节点v的平均接收信噪比
其中Cw，v=∏z≠u，v，wz∈Nγ—w，vγ—w，v-γ—z，v，Y表示随机事件，y表示随机事件中的一个具体事例，N表示发射节点的集合.
为了提升WSN在运行过程中的通信质量，减小节点的死亡速度，目标是将SN分配到最接近的RN，使成员节点的能量消耗最小.在满足通信要求的情况下，部署最少数量的RNs以覆盖所有的传感区域是首要目标.为了得到RN的最优化放置位置，考虑了通信质量、网络覆盖范围和信号接收概率.通过将SN分配到最接近的RN，最大限度提高WSN的寿命，解决集群形成的问题，最终将问题转化成簇内通信距离最小化的问题.
WSN能量的消耗将会随成员节点与其对应RN距离的增加而增大.其距离
其中（xu，yu，hu），（Xv，Yv，Hv）是节点su和中继节点RNv的坐标.
假设传感范围是面积为B的正方形区域，则节点u的最大通信半径为ρu，可以覆盖的区域面积为πρ2u.
令αuv为每个传感器节点分配给相应簇头的判断因子，它是一个布尔型变量，当节点su所对应的簇头是RNv时，αuv=1；否则αuv=0.
在确保通信质量的情况下，使网络的数据传输距离最小.即求
其中限制条件（13）～（16）式分别保证了每个SN可以分配给一个RN，每个SN必须在一个RN的传输范围ρu内，每一次的发射信号能被成功接收以及决定系数αuv为布尔型.
3结果仿真与分析
为验证本算法相对于不考虑物理层因素的传统中继放置算法的优越性，对算法的性能进行仿真.仿真实验的区域面积为100 m×100 m，SN的个数为80，RN预先设定的放置位置个数为5，SN采用均匀部署方式.图2给出了一步受限RN放置（OSRP）算法[6]和本算法在SN在传包效率上的仿真，图3比较了OSRP算法和本算法在传感网生命周期方面的性能.
由图2可以看出，本算法相对于OSRP算法减少了SN的重传次数，使传包效率得到提升.从图3 SN数随时间的变化曲线可以看出4 h之后，相对于OSRP算法，本算法有效地减少了SNs的死亡个数，延长了网络生命周期.
4结论
针对在双层受限结构的WSN中，传统的RN放置算法会导致丢包率高和网络生命周期短的问题，本文作者提出了基于MIPS的RN放置算法.该算法考虑了RN放置的物理层因素，改善了网络通信质量，提升了传包效率，延长了WSN的生命周期.因此对于双层受限结构的WSN来说，本算法是一种较好的RN放置方案.
参考文献：
[1]Tripathi A，Gupta P，Trivedi A，et al.Wireless sensor node placement using hybrid genetic programming and genetic algorithms [J].International Journal of Intelligent Information Technologies，2011，7（2）：63-83.
[2]Bari A，Jaekel A，Jiang J，et al.Design of fault tolerant wireless sensor networks satisfying survivability and lifetime requirements [J].Computer Communications，2012，35（3）：320-333.
[3]Iqbal Z，Kim K，Lee H N.A cooperative wireless sensor network for indoor industrial monitoring [J].IEEE Transactions on Industrial Informatics，2017，13（2）：482-491.
[4]Cheng X Z，Du D Z，Wang L S，et al.Relay sensor placement in wireless sensor networks [J].Wireless Networks，2008，14（3）：347-355. [5]Misra S，Hong S D，Xue G L，et al.Constrained relay node placement in wireless sensor networks：formulation and approximations [J].IEEE/ACM Transactions on Networking，2010，18（2）：434-447.
[6]Chelli A，Bagaa M，Djenouri D，et al.Onestep approach for twotiered constrained relay node placement in wireless sensor networks [J].IEEE Wireless Communications Letters，2016，5（4）：448-451.
[7]Gao Z P，Chen K，Qiu X S.Relay node placement with base stations in wireless sensor networks faulttolerant [J].Chinese Journal of Electronics，2014，23（4）：794-800.
[8]Lin G H，Xue G L.Steiner tree problem with minimum number of Steiner points and bounded edgelength [J].Information Processing Letters，1999，69（2）：53-57.
[9]Souissi M，Meddeb A.Modelling of clustering with relay nodes in Wireless Sensor Networks [C].Proceedings of the 7th Annual Computing and Communication Workshop and Conference，Las Vegas：IEEE，2017.
[10]Simon M K，Alouini M S.Digital communication over fading channels [M].2nd ed.Hoboken：Wiley，2005.
[11]Molisch A F.Wireless communications [M].Hoboken：Wiley，2005.
（責任编辑：包震宇，郁慧）
关键词：
中继节点； 无线传感器网络； 双层受限； 整数线性规划
中图分类号： TN 929.5文献标志码： A文章编号： 10005137（2018）02022005
Research on the placement algorithm of twotiered constrained
relay nodes in wireless sensor networks
Xiang Haokai， Zhou Xiaoping*， Wang Jianan， Li Li， Huang Jiahui
（The College of Information，Mechanical and Electrical Engineering，Shanghai Normal University，Shanghai 200234，China）
Abstract：
In threedimensional space，when the location of relay nodes is limited and it is a twolayer topology，a relay location algorithm based on mixed integer linear programming （MILP） is proposed.The algorithm first considers the physical layer model placed by relay nodes in threedimensional space.Then，the optimal energy efficient clustering is given based on mixed integer linear programming.So that the transmission distance between each sensor node and its corresponding cluster head is the minimized.The simulation results show that compared with the traditional relay node algorithm that only considers the minimum intra cluster distance，the algorithm has a great improvement in reducing the retransmission rate and prolonging the life cycle of the network.
Key words：
relay node； wireless sensor networks； twotiered constrained； mixed integer linear programming
收稿日期： 20171227
基金項目： 上海市自然科学基金项目（16ZR1424500）
作者简介： 向浩凯（1993-），男，硕士研究生，主要从事无线传感器网络方面的研究.Email：2283557476@qq.com
导师简介： 周小平（1981-），男，博士，副教授，主要从事宽带无线通信、新一代移动通信和物联网技术方面的研究.Email：zxpshnu@163.com
*通信作者
引用格式： 向浩凯，周小平，王家南，等.无线传感器网络中双层受限中继节点放置算法研究 [J].上海师范大学学报（自然科学版），2018，47（2）：220-224.
Citation format： Xiang H K，Zhou X P，Wang J N，et al.Research on the placement algorithm of twotiered constrained relay nodes in Wireless Sensor Networks [J].Journal of Shanghai Normal University （Natural Sciences），2018，47（2）：220-224.
0引言
网络节点的合理布局是无线传感器（WSN）网络运行的首要前提.在WSN的大多数应用场景中，传感器节点（SN）和网关节点（GN）的布局位置相对固定，并且它们的能量往往难以补充，为了延长网络生命周期，提升网络连通性与可靠性，可以通过放置中继节点（RN）的方式来实现[1].因此，中继节点布局的优劣往往决定了无线传感器网络的生命周期、通信质量[2].
RN的布局分为单层网络结构（singletiered）和双层网络结构（twotiered）两种[3].在单层网络结构中，SN和RN都需要转发数据，而在双层网络结构中，SN只需要将自身采集的数据传送给RN，不需要转发其他传感器节点的数据.文献[4]对于单层网络结构的情况，将最少放置RN的问题转化成一个Steiner树的问题，解出最小化的Steiner点数和边长，便可得到最小放置RN的个数和位置.文献[5]对于文献[4]中的RN放置位置不受限的问题进行改进，中继节点只能放置在预先设定的位置上，给出了基于多项式时间复杂度的近似算法. 文獻[6]提出了一步受限RN放置算法，保证SN与基站相连接的情况下放置最小数量的中继节点.针对文献[6]没有考虑网络的容错性能，文献[7]和[8]在满足网络容错需求的情况下，基于Steiner树的理论给出最小数量放置RN的探索式算法.
上述文献主要基于簇内距离最小化来实现RN的最优化放置，没有将物理因素的影响考虑在内.本文作者考虑在三维空间中，物理层参数（信道衰落和信噪比）对RN放置的影响，给出基于瑞利衰落的现实物理层模型；同时，基于混合整数线性规划（MIPS），得到SN与其簇头之间传输距离的最小值，从而在满足通信要求的前提下，得到RN的最优化放置位置.
1系统模型
本研究场景的系统模型如图1所示，其中RN作为簇头，负责收集来自SN的数据并将其转发到基站，对于此问题，需要找到最优化的RN部署方案，使每一个传感器都与基站连接.
基站与基站之间是通过有线的方式连接的，u代表发射节点，v代表接收节点，发射功率分别为Pu和Pv，两个节点之间的信道增益为au，v，瑞利块衰落在同一个块中信道增益保持常量.在本系统中，考虑了其他节点对节点v的干扰，节点w对节点v的衰减系数为aw，v，服从瑞利分布.从节点v所获得的接收信号
2双层受限RN放置算法
为了能够最优化放置RN，减少所提方案的复杂度，假设节点u的发射范围为ρu，它的大小由节点发射功率决定，也就是说当节点v与节点u之间的距离不超过ρu，那么节点u就能把节点v选作为父节点.
由（4），（5）式可知，节点v的平均接收信噪比
其中Cw，v=∏z≠u，v，wz∈Nγ—w，vγ—w，v-γ—z，v，Y表示随机事件，y表示随机事件中的一个具体事例，N表示发射节点的集合.
为了提升WSN在运行过程中的通信质量，减小节点的死亡速度，目标是将SN分配到最接近的RN，使成员节点的能量消耗最小.在满足通信要求的情况下，部署最少数量的RNs以覆盖所有的传感区域是首要目标.为了得到RN的最优化放置位置，考虑了通信质量、网络覆盖范围和信号接收概率.通过将SN分配到最接近的RN，最大限度提高WSN的寿命，解决集群形成的问题，最终将问题转化成簇内通信距离最小化的问题.
WSN能量的消耗将会随成员节点与其对应RN距离的增加而增大.其距离
其中（xu，yu，hu），（Xv，Yv，Hv）是节点su和中继节点RNv的坐标.
假设传感范围是面积为B的正方形区域，则节点u的最大通信半径为ρu，可以覆盖的区域面积为πρ2u.
令αuv为每个传感器节点分配给相应簇头的判断因子，它是一个布尔型变量，当节点su所对应的簇头是RNv时，αuv=1；否则αuv=0.
在确保通信质量的情况下，使网络的数据传输距离最小.即求
其中限制条件（13）～（16）式分别保证了每个SN可以分配给一个RN，每个SN必须在一个RN的传输范围ρu内，每一次的发射信号能被成功接收以及决定系数αuv为布尔型.
3结果仿真与分析
为验证本算法相对于不考虑物理层因素的传统中继放置算法的优越性，对算法的性能进行仿真.仿真实验的区域面积为100 m×100 m，SN的个数为80，RN预先设定的放置位置个数为5，SN采用均匀部署方式.图2给出了一步受限RN放置（OSRP）算法[6]和本算法在SN在传包效率上的仿真，图3比较了OSRP算法和本算法在传感网生命周期方面的性能.
由图2可以看出，本算法相对于OSRP算法减少了SN的重传次数，使传包效率得到提升.从图3 SN数随时间的变化曲线可以看出4 h之后，相对于OSRP算法，本算法有效地减少了SNs的死亡个数，延长了网络生命周期.
4结论
针对在双层受限结构的WSN中，传统的RN放置算法会导致丢包率高和网络生命周期短的问题，本文作者提出了基于MIPS的RN放置算法.该算法考虑了RN放置的物理层因素，改善了网络通信质量，提升了传包效率，延长了WSN的生命周期.因此对于双层受限结构的WSN来说，本算法是一种较好的RN放置方案.
参考文献：
[1]Tripathi A，Gupta P，Trivedi A，et al.Wireless sensor node placement using hybrid genetic programming and genetic algorithms [J].International Journal of Intelligent Information Technologies，2011，7（2）：63-83.
[2]Bari A，Jaekel A，Jiang J，et al.Design of fault tolerant wireless sensor networks satisfying survivability and lifetime requirements [J].Computer Communications，2012，35（3）：320-333.
[3]Iqbal Z，Kim K，Lee H N.A cooperative wireless sensor network for indoor industrial monitoring [J].IEEE Transactions on Industrial Informatics，2017，13（2）：482-491.
[4]Cheng X Z，Du D Z，Wang L S，et al.Relay sensor placement in wireless sensor networks [J].Wireless Networks，2008，14（3）：347-355. [5]Misra S，Hong S D，Xue G L，et al.Constrained relay node placement in wireless sensor networks：formulation and approximations [J].IEEE/ACM Transactions on Networking，2010，18（2）：434-447.
[6]Chelli A，Bagaa M，Djenouri D，et al.Onestep approach for twotiered constrained relay node placement in wireless sensor networks [J].IEEE Wireless Communications Letters，2016，5（4）：448-451.
[7]Gao Z P，Chen K，Qiu X S.Relay node placement with base stations in wireless sensor networks faulttolerant [J].Chinese Journal of Electronics，2014，23（4）：794-800.
[8]Lin G H，Xue G L.Steiner tree problem with minimum number of Steiner points and bounded edgelength [J].Information Processing Letters，1999，69（2）：53-57.
[9]Souissi M，Meddeb A.Modelling of clustering with relay nodes in Wireless Sensor Networks [C].Proceedings of the 7th Annual Computing and Communication Workshop and Conference，Las Vegas：IEEE，2017.
[10]Simon M K，Alouini M S.Digital communication over fading channels [M].2nd ed.Hoboken：Wiley，2005.
[11]Molisch A F.Wireless communications [M].Hoboken：Wiley，2005.
（責任编辑：包震宇，郁慧）