2016, Vol. 49文章信息
- 钱建生, 孙永
- QIAN Jiansheng, SUN Yong
- 煤矿井下无线传感器网络分布式信道快速分配算法
- Distributed channel fast allocation in wireless sensor network QIAN Jiansheng, SUN Yong
- 武汉大学学报(工学版), 2016, 49(3): 458-464
- Engineering Journal of Wuhan University, 2016, 49(3): 458-464
- http://dx.doi.org/10.14188/j.1671-8844.2016-03-024
-
文章历史
- 收稿日期: 2015-09-27
支持多通信接口(Multi-Radio)的无线传感器网络[1, 2]因具有中继通信零延迟的特点非常适合作为对数据传输可靠性和实时性有苛刻要求的煤矿井下安全监测监控系统[3]中数据采集和传输的无线主干网络.而无线传感器网络节点实现并发通信的另一个重要条件是为该节点的多通信接口分配互不相同的通信信道.否则，节点首先就会因自身发射端的同信道无线干扰无法接收外源信号而导致通信失败.合理的信道分配不仅对无线传感器网络节点本身很重要，同时可以降低甚至消除无线传感器网络节点间的通信干扰.因此，许多学者致力于无线传感器网络中信道分配策略的研究.
赵军[4]等提出了适用于快速移动节点的集中式信道分配算法.陈珊珊[5]等则提出了一种集中式自适应信道分配算法DNAF(Densest Nearest Assignment First).王子凡[6]等则设计了一种基于干扰感知的多接口动态信道分配算法.然而，由于存在算法复杂度低、网络健壮性强和易扩展等优势，分布式信道分配算法吸引了更多学者的关注和研究.
Hao等首先提出了基于节点间协作的分布式信道分配算法[7].针对节点间相当数量的信息交换耗能较多的情况，其后提出了基于虚拟博弈[8]的非协作的信道分配算法[9].其在信道分配和功率控制相互关系深入分析和研究的基础上，运用效用函数解决了二者的联合优化问题.戴昊峰等在信道分配中运用了完美博弈[10]和不完美博弈[11]的思想，利用位势博弈特性构建效用函数，对存在潜在干扰的链路分配信道，使实际干扰最小.胡洁[12]等针对实际分布式网络中节点通信受限的特点,设计了基于一致性的拍卖算法CDACA(Consensus-Based Decentralized Auctions for Channel Assignment).但是，基于物理叠加干扰模型的算法复杂，并不适用于能量受限且节点运算处理能力有限的无线传感器网络.
Saifullah等在链路干扰模型的基础上将信道分配算法划分为基于节点的信道分配算法和基于链路的信道分配算法，并分别提出了基于节点的和基于链路的无干扰分布式信道分配算法Dis-Link[13].而基于链路的信道分配算法比基于节点的信道分配算法更具灵活性，因而更适用于多通信接口(Multi-Radio)的无线传感器网络.
Dis-Link是建立在数据链路层的无干扰分布式信道分配算法，并未涉及和实际应用紧密相关的物理层功率控制相关问题的讨论和算法的具体实现，同时也存在算法收敛速度慢、执行效率低下的缺点.本文在深入分析现有的分布式信道分配算法的基础上提出了基于网络拓扑最大链路数的分布式信道分配算法CALENT，性能更为优越.
1 网络模型无线传感网络由作为该网络数据汇聚的基站和若干无线传感器节点组成.数据链路e(u,v)表示数据由节点u发出并由节点v接收.干扰链路c(u,v)则意味着节点u的数据发送会干扰节点v数据接收并直接导致节点v数据接收失败.在相同信道上并发的两条数据链路，如果存在任一条的发送节点到另一条的接收节点的干扰链路，则该两条数据链路存在冲突，即任一条链路的数据发送均会导致另一条链路的数据接收失败.在无线传感网络中，如果任意两个无线传感器节点均不存在干扰链路，则定义该无线传感网络是无冲突无线传感网络.
我们采用链路干扰图来对无线传感网络建立系统模型.在链路干扰图G=(V,E)中：V代表无线传感器节点的集合，同时包含数据汇聚节点s(基站)；E表示数据链路和潜在干扰链路的集合.定义无线传感网络生成树节点的干扰节点集合为C(u,f)，无线传感网络通过信道分配算法f成为无冲突无线传感网络的条件就是使任意两个无线传感器节点均不存在干扰链路，即：
鉴于无线信道作为有限且珍贵的无线资源，无线传感网络信道分配的目的是解决在无干扰前提下的所需信道的优化问题，即寻求满足任意两个无线传感器节点均不存在干扰链路条件下所需信道总数的最小值.其目标函数为：
网络模型中的干扰链路则由相应的干扰模型来进行确定.特定的干扰模型确定了网络链路的干扰范围，不同的干扰模型应用其链路形成的干扰范围亦不相同.
2 干扰模型根据无线电环境干扰分析侧重点的不同，Gupta等[14]首先区分并提出了物理和协议两类干扰模型.随着研究的深入，功率控制和冲突避让等机制陆续被提出和应用以降低物理干扰对网络性能的影响.为进一步分析研究协议的干扰效应，学者细化并提出了接收者协议干扰模型[14](Receiver-based Protocol Interference Model)、发送者协议干扰模型[15](Sender-based Protocol Interference Model)和链路协议干扰模型[16](Link-based Protocol Interference Model)3类协议干扰模型.本文采用接收者协议干扰模型确定网络模型中的干扰链路(如图 1).
|
| 图 1 接收者协议干扰模型 Figure 1 Receiver-based protocol interference model |
接收者协议干扰模型研究接收节点不受干扰成功接收数据的条件.假设发射节点Xi(i∈T)通过无线电发送数据给接收节点Xj(j≠i,j∈T)，则接收节点Xk(k≠i,k≠j,k∈T)不受发射节点Xi(i∈T)干扰的条件是：
其中:Δ为避免多节点叠加干扰人为设置的环状保护隔离区归一化(环形内半径为1)的半径差值.根据文献[17]中煤矿井下实践经验，本文中参数Δ取值为0.3.
3 最小功率控制无线传感网络中无线传感器节点的发射功率不仅可以延长该能量受限的特殊网络的寿命，同时可以降低对其他节点产生同信道间的信号干扰，提高信道复用率，节约宝贵的信道资源.然而过低的信号接收强度和信噪比也会导致接收端无法进行正确的信道解码和接收数据.因此，需确定无线传感器节点的最低发射功率以保证无线传感器节点间的正常通信.
当接收信号强度大于等于Pth时，信号内包含的数据才能被成功解码和接收.假设发送节点的信号发射功率为Pt0，目的节点的信号接收功率为Pr0，则发送节点的最低发射功率Pmin由下式确定：
因此，无线传感节点间只需约定初始信号发射功率，就可以根据信号的初始接收功率确定最低发射功率.
4 信道分配算法虽然无线传感器网络的拓扑结构直接影响所需最少信道总数目和信道分配的最终结果，但本文依然决定暂时避开对无线网络拓扑结构算法的探讨并假定无线传感器网络的拓扑结构在信道分配前已确定，即无线传感器网络各个节点已存储在无线网络拓扑形成阶段确定的全网各个节点(包含基站)的邻居节点(父节点和子节点)个数的最大值和与自身节点有数据链路关系的邻居节点的具有全网唯一标识ID以及相应的最小通信发射功率.该分布式信道分配算法CALENT步骤如下：
初始化：无线传感器网络任意节点u∈v初始化本地节点信道重选标志和子节点信道重选标志表为1，循环跳出标志、并行循环体1跳出标志和并行循环体2跳出标志为0以及本地编号从1至N0的信道占位记录表(初始值为0).在信道编号1至信道编号N0随机选择一个信道作为其初始选择信道并在具有相同信道编号的信道占位表新增本地节点ID和信道重选标志位记录.
并行循环体11) 发送信标脉冲信号：无线传感器网络中各个节点u∈V以1倍相应的最小通信发射功率周期性地在信道1上向父节点发送包含源节点ID(自身ID)、目标节点ID(父节点ID)、本地节点信道重选标志位以及当前轮选定的数据通信信道编号的信标脉冲信号.为避免各个节点的信标脉冲信号的同信道冲突，不同的信标脉冲信号周期在合理数值范围内取随机值.需要注意的是，作为根节点的基站(无父节点)并不发送信标脉冲信号.
2) 跳出并行循环体1：若本地节点信道重选标志位为0，则并行循环体1跳出标志位值置1.若并行循环体1跳出标志位和并行循环体2跳出标志均为1，则跳出循环体1.
3) 接收反馈脉冲信号：无线传感器网络中各个节点u∈V在自身发送信标脉冲信号的间隙在信道1上监听和接收其父节点发送来的包含源节点ID(自身ID)、目标节点ID(子节点ID)、相应子节点信道重选标志位以及当前选定的数据通信信道编号的反馈脉冲信号.需要注意的是，作为根节点的基站(无父节点)并不接收反馈脉冲信号.反馈脉冲信号中判断子节点信道重选标志位，若为1，则本地节点信道重选标志位值置1，然后把反馈脉冲信号中重选后的信道编号作为本地节点新一轮选定的数据通信信道，并在本地信道占位记录表中更新本地节点ID和信道重选标志位记录：在信道占位记录表中查找并删除本地节点ID原记录，在当前具有相同信道编号的信道占位记录表中新增本地节点ID和信道重选标志位记录.最后跳转步骤1)进入循环体1下一轮循环.若为0，则本地节点信道重选标志位值置0.
并行循环体21) 接收信标脉冲信号：无线传感器网络中除叶子节点(无子节点)的各个节点和作为根节点的基站在自身发送信标脉冲信号的间隙在信道1上监听和接收其他节点发送信标脉冲信号.在每成功接收一次信标脉冲信号后，在信道占位记录表中新增或更新源节点ID和信道重选标志位记录：查找全部本地信道占位记录表中是否包含源节点ID，如不存在则在具有相同信道编号的信道占位表中增加源节点ID和信道重选标志位记录(新增记录)；如存在则在信道占位记录表中查找并删除源节点ID和信道重选标志位原记录，在当前具有相同信道编号的信道占位记录表中新增源节点ID和信道重选标志位记录(更新记录).需要注意的是，叶子节点(无子节点)并不接收信标脉冲信号.如信道占位表包含全部子节点ID记录且当前所有信道占位记录表中信道重选标志位均为0则将循环跳出标志位值置1.
2) 信道重选判断：当无线传感器网络中除叶子节点(无子节点)的各个节点和作为根节点的基站成功接收并处理信标脉冲信号后，判断各子节点ID和信道重选标志位记录所在信道占位记录表的记录数，如大于1则将该子节点信道重选标志位值置1；如等于1则将该子节点信道重选标志位值置0，保持当前轮选定的数据通信信道编号为下一轮选定的数据通信信道编号，并跳转步骤4).
3) 信道重选操作：当各子节点信道重选标志位为1时执行信道重选操作.检查本地信道占位表是否仅含记录为0的空闲可用信道，如有则随机选择本地信道占位表中仅有记录为0的空闲可用信道编号作为子节点新一轮选定的数据通信信道.否则增加信道编号M为的信道作为新一轮选定的数据通信信道，在本地新增信道编号M为信道占位表并新增该子节点ID和信道重选标志位记录.
4) 发送反馈脉冲信号：无线传感器网络中除叶子节点(无子节点)的各个节点和作为根节点的基站以倍相应的最小通信发射功率周期性地在信道1上发送包含源节点ID(自身ID)、目标节点ID(子节点ID)、相应子节点信道重选标志位以及当前选定的数据通信信道编号的反馈脉冲信号.为避免各个节点的反馈脉冲信号的同信道冲突，不同的反馈脉冲信号周期在合理数值范围内取随机值.需要注意的是，叶子节点(无子节点)并不发送反馈脉冲信号.
5) 循环或跳出循环体2：若所有子节点信道重选标志位非全0或循环跳出标志位为0，则跳转步骤1)进入循环体2下一轮循环；若所有子节点信道重选标志位均为0且循环跳出标志位为1，则并行循环体2跳出标志位值置1.
若并行循环体1跳出标志位和并行循环体2跳出标志均为1，则跳出循环体2.
5 仿真分析假设在100 m×100 m的正方形二维平面区域内随机位置放入100个无线传感器节点，作为数据汇聚点的基站位于正方形区域中心点处即坐标位置为(50,50).平面分布图如图 2所示.
|
| 图 2 无线传感器节点和基站分布图 Figure 2 Distribution of sensor nodes and base station |
图 2中，实心圆点为无线传感器节点，每个节点右侧的编号是其节点ID，编号范围从1到100.图中心处×状符号表示作为数据汇聚点的基站所处位置.
无线传感器节点以一定规则通过自组网方式形成无线传感器网络.其网络架构如图 3所示.
|
| 图 3 无线传感器网络架构 Figure 3 Structure of wireless sensor network |
从图 3可以很容易地看出邻居节点(父节点和子节点)个数最多的是节点ID编号为28的节点，其个数为4，即N0=4.
为体现CALENT分布式信道分配算法的优越性，本文以Saifullah提出的无干扰分布式信道分配算法Dis-Link[8]为对照，深入研究并对比分析CALENT分布式信道分配算法在相同网络分布架构和相同初始条件下同信道干扰指数和算法收敛速度等方面的优势.
定义同信道干扰指数为在本轮信道分配算法执行后全网因同信道干扰仍需要重选信道的节点个数.CALENT和Dis-Link算法在信道分配过程中每轮同信道干扰指数变化趋势和对比如图 4所示.
|
| 图 4 同信道干扰指数对比图 Figure 4 Co-channel interference index comparison between Dis-Link and CALENT |
由图 4可以看出，CALENT和Dis-Link算法的无线传感网络节点间的同信道干扰指数在初始状态下(第0回合)即体现出差异.Dis-Link算法的初始同信道干扰指数为100，CALENT算法则仅为57.对比算法初始信道分配图可以很直观地看出这一差异产生的原因.Dis-Link和CALENT算法的初始信道分配对比如图 5所示.
|
| 图 5 初始信道分配对比图 Figure 5 5 Initial channel allocation comparison between Dis-Link and CALENT |
由图 5可以看出，Dis-Link算法定义全网节点全部选择信道1作为其初始信道，因全部节点均选择相同的初始信道(信道1)导致网内的所有节点都会受到其他节点的同信道干扰，故Dis-Link算法的初始同信道干扰指数等于网内节点总数即为100.深入的理论分析和研究表明，满足无干扰的充要条件是连接同一节点的任意两条链路都必须分配不同编号的信道.这样该网络节点具有最大的边数即是该网络无干扰信道分配信道数的理论最小值，即Nmin=N0.而CALENT算法则是巧妙地利用了无线传感器网络拓扑结构的这一特征，扩大初始可选信道的上限值，通过在理论范围内分配不同的初始信道避免同信道干扰，使得初始同信道干扰指数有效地降低至57.有效地规避同信道干扰即意味着降低信道需要重新选择的概率，这直接提高了信道分配的效率，大大缩短了全网信道分配的时间.Dis-Link算法的同信道干扰指数首先在第18轮降至0(相应地Dis-Link算法的同信道干扰指数在其后的第35轮成功收敛于0)，即全网不再存在同信道干扰，同时意味着CALENT算法因满足信道分配的既定要求而有效结束，即CALENT算法的快速收敛性在此得到实验证实.
Dis-Link和CALENT算法的最终信道分配收敛结果如图 6所示.
由图 6可以看出，Dis-Link算法和CALENT算法的信道分配的最终结果虽然不同，但是所需最小信道数均为6且都实现了全网同信道零干扰的分配目标，均为有效信道分配结果.同时，该结果也反映了即便无线网络拓扑结构固定不变，信道分配也具有普遍多样性.
|
| 图 6 信道分配对比图 Figure 6 Channel allocation comparison between Dis-Link and CALENT |
同样，Dis-Link和CALENT算法的收敛速度亦具有非唯一的特性.Dis-Link和CALENT算法在上述网络拓扑结构不变的条件下重复100次信道分配的算法收敛速度和满足全网同信道零干扰约束下所需信道总数最小值的统计结果如图 7所示.
|
| 图 7 收敛速度和最小信道数统计结果 Figure 7 Statistics of convergence rate and minimum number of channel(s) |
由图 7(a)可以看出，Dis-Link算法的收敛轮数分布多处在20~40之间，而CALENT算法的收敛轮数分布则处于10~25较低的位置.Dis-Link算法的收敛轮数统计平均值为28，而CALENT算法的收敛轮数统计平均值为19.CALENT算法的平均收敛速度比Dis-Link算法的平均收敛速度提高了32%.由此统计条件下的CALENT算法快速收敛的稳定性在此得到实验证实.
由图 7(b)可以看出，Dis-Link和CALENT算法满足全网同信道零干扰约束下所需信道总数最小值均保持稳定在6，由此统计条件下的CALENT算法所需最小信道数的稳定性在此得到实验证实.
6 结论本文在深入分析现有的分布式信道分配算法的基础上结合无线传感器网络节点分布的特点和网络架构等特征，提出了基于网络拓扑最大链路边数的分布式信道分配算法CALENT.同时确定了和物理层相关的无线传感器网络节点最小发射功率和具体的算法实现步骤.通过与现有的无干扰分布式信道分配算法Dis-Link的深入分析和对比研究表明，CALENT算法在同信道干扰指数和算法收敛速度等方面具有明显的优势，性能更为优越.
| [1] |
王昊, 李舸, 石劲涛. 多接口无线网络信道分配与路由技术研究[J].
科技资讯, 2014, 35: 24–25.
Wang Hao, Li Ge, Shi Jintao. Research on channel allocation and routing technology in multi-interface wireless network[J]. Science & Technology Information, 2014, 35: 24–25. |
| [2] | Campbell C A, Khan S, Singh D, Loo K K. Multi-channel multi-radio using 802[J]. Multi-channel multi-radio using 802 11 based media access for sink nodes in wireless sensor networks, 2011, 11(5): 4917–4942. |
| [3] |
闫冰. 煤矿安全监测监控系统在井下的应用与分析[J].
技术与市场, 2014, 10: 126.
Yan Bing. Coal mine safety monitoring system in underground analysis and application[J]. Technology and Market, 2014, 10: 126. |
| [4] |
赵军, 陈祥光, 刘春涛, 余向明, 岳彬. 集中式信道分配算法在WSN移动节点中的应用研究[J].
北京理工大学学报, 2011, 11: 1322–13261341.
Zhao Jun, Chen Xiangguang, Liu Chuntao, Yu Xiangming, Yue Bin. Study on centralized channel assignment algorithm for mobile nodes in wireless sensor networks[J]. Transactions of Beijing Institute of Technology, 2011, 11: 1322–13261341. |
| [5] |
陈珊珊, 郭宇春, 张有根. 基于初始化AP的自适应信道分配算法[J].
计算机技术与发展, 2014, 11: 5–8.
Chen Shanshan, Guo Yuchun, Zhang Yougen. Adaptive channel allocation algorithm based on initialization of AP[J]. Computer Technology and Development, 2014, 11: 5–8. |
| [6] |
王子凡, 刘作学, 代健美. 基于干扰感知的多接口无线Mesh网络信道分配算法[J].
现代电子技术, 2014, 14: 24–27.
Wang Zifan, Liu Zuoxue, Dai Jianmei. Interference-aware based channel assignment algorithm for multi-interface wireless mesh networks[J]. Modern Electronics Technique, 2014, 14: 24–27. |
| [7] | Hao Xiaochen, Zhang Yaxiao, Liu Bin. Distributed cooperative control algorithm for topology control and channel allocation in multi-radio multi-channel wireless sensor network: from a game perspective[J]. Wireless Personal Communications, 2013, 73(3): 353–379. DOI:10.1007/s11277-013-1192-y |
| [8] | Hao Xiaochen, Zhang Yaxiao, Jia Nan, Liu Bin. Virtual game-based energy balanced topology control algorithm for wireless sensor networks[J]. Wireless Personal Communications, 2013, 69(4): 1289–1308. DOI:10.1007/s11277-012-0634-2 |
| [9] | Hao Xiaochen, Gong Qianqian, Hou Shuang, Liu Bin. Joint channel allocation and power control optimal algorithm based on non-cooperative game in wireless sensor networks[J]. Wireless Personal Communications, 2014, 78(2): 1047–1061. DOI:10.1007/s11277-014-1800-5 |
| [10] |
戴昊峰, 何世彪, 韩辉, 张晖, 谭冕. 基于完美信息博弈的多无线电信道分配算法[J].
电视技术, 2014, 13: 103–107.
Dai Haofeng, He Shibiao, Han Hui, Zhang Hui, Tan Mian. Multiple radio channel assignment based on perfect game theory[J]. Video Engineering, 2014, 13: 103–107. |
| [11] |
戴昊峰, 何世彪, 谭冕, 郑鹏宇, 张晖. 一种基于不完美信息博弈的多冲突域信道分配算法[J].
电信科学, 2014(5): 112–119.
Dai Haofeng, He Shibiao, Tan Mian, Zheng Pengyu, Zhang Hui. A multiple collision channel assignment based on imperfect game theory[J]. Telecommunications Science, 2014(5): 112–119. |
| [12] |
胡洁, 赵祚喜, 陈润恩. 分布式网络中基于一致性的信道分配算法[J].
电子学报, 2014(6): 1132–1138.
Hu Jie, Zhao Zuoxi, Chen Runen. Consensus-based channel assignment in decentralized network[J]. Acta Electronica Sinica, 2014(6): 1132–1138. |
| [13] | Saifullah Abusayeed, Xu You, Lu Chenyang, Chen Yixin. Distributed channel allocation protocols for wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(9): 2264–2274. DOI:10.1109/TPDS.2013.185 |
| [14] | Gupta P, Kumar P R. The capacity of wireless networks[J]. IEEE Transaction on Information Theory, 2000, 46(2): 388–404. DOI:10.1109/18.825799 |
| [15] | Yi S, Pei Y, Kalyanaraman S. On the capacity improvement of ad hoc wireless networks using directional antennas[C]//Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing, Annapolis, Maryland, USA,2003: 108-116. http://cn.bing.com/academic/profile?id=2166640289&encoded=0&v=paper_preview&mkt=zh-cn |
| [16] | Kumar V S A, Marathe M V, Parthasarathy S, et al. End-to-end packet scheduling in wireless ad hoc networks[C]//Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, USA, 2004: 1021-1030. http://cn.bing.com/academic/profile?id=1547576067&encoded=0&v=paper_preview&mkt=zh-cn |
| [17] |
冯小龙. 矿井无线Mesh网络关键技术及应用[D].徐州:中国矿业大学,2011.
Feng Xiaolong. The key technologies and application of mine wireless mesh network[D]. Xuzhou: China University of Mining and Technology,2011. |