宋　宇，陈　剑，威　力，刘　炯

（1.西安通信学院，西安　710106；2.解放军理工大学指挥信息系统学院，南京　210007）



适用于认知无线传感器网络的高效频谱分配方法*

宋宇1，2，陈剑2，威力2，刘炯1

（1.西安通信学院，西安710106；2.解放军理工大学指挥信息系统学院，南京210007）

摘要：广泛工作在ISM（Industrial，Scientific and Medical）频段的无线传感器网络面临严重的频谱稀缺问题。在无线通信中，动态频谱分配被认为是提高频谱效能的重要途径。针对典型集中式管理的认知无线传感器网络设计了基于图着色结合负载强度的高效频谱分配算法。首先在协议干扰模型下确保频谱资源在空间上充分利用，随后综合考虑节点负载强度与公平性建立优化模型并按照乘子法加拟牛顿法框架求解最优值。仿真实验表明算法与固定频谱分配方式和传统自适应频谱分配算法相比，在系统吞吐量和节点缓冲区队列长度两个关键性能指标上具有显著优势。

关键词：认知无线传感器网络，频谱效能，图着色，自适应，凸规划

0　引言

认知无线电作为目前提高频谱利用效能的主要技术发展方向［1］，可以从时间和空间上挖掘和利用空闲频谱。为此，认知无线传感器网络（Cognitive WSN，CWSN）概念油然而生［2］，并被认为是与其他工作于ISM频段的其他网络（如WiFi，Bluetooth，Zigbee等）共享稀缺频谱资源的一种重要解决途径。CWSN相对于WSN来说，传感器节点附加了一个感知（或被分配）频谱的阶段，随后利用该频谱资源按照网络拓扑建立通信连接。

根据分配方式的不同，频谱分配主要可分为分布式和集中式两类。在分布式机制中，每个传感器节点必须具备感知全局或者局部空间可用频谱的能力，并执行竞争，博弈以及协同等操作实现频谱效用的最优或者次优［3］。但是传感器节点能量受限约束往往难以应对分布式频谱分配所带来的巨大通信开销。在许多应用场合中，集中式的在全网部署一个专门网络协调器（Network Coordinator）更加适合［4-5］，网络协调器收集各传感器节点的链路状态，频谱需求等信息，根据相关准则执行频谱分配决策以及协调各传感器节点机会的频谱使用。比较有代表性的工作有：Rayanchu等人针对集中式企业无线网络提出了一种报文传输调度和频谱分配联合优化算法［6］，通过构建链路冲突模型，预测不同信道频宽组合下的网络并发传输容量，结合报文传输调度的优化，可以大幅提升系统吞吐量。Chen等人针对集中式的无线网络提出一种速率控制和频谱分配联合解决方案［7］，该方案通过引入虚拟子网队长的概念来衡量AP负载，据此调整AP的信道频宽，结合传输速率控制，在优化系统吞吐量的同时减少传输时延。Murty等设计并实现的一种基于地理位置的频谱分配系统等［8］。

与上述研究工作不同，本文针对传感器网络典型部署场景，综合考虑传感器网络采集节点的空间位置以及负载大小，实现频谱复用的同时优化频谱效能，兼顾节点公平性，仿真实验表明，该方法在网络吞吐率和节点缓冲区队列长度两个指标上具有明显优势。

1　系统模型及问题描述

在报文传输中，每个用户维持缓冲报文队列，其值反映用户对汇聚节点产生的负载大小，本文关于负载强度的定义见3.1节。

图1典型传感器网络拓扑模型

典型无线传感器网络拓扑模型主要包括3个组件：汇聚节点（网络协调器），中继节点以及采集节点。如图1所示，将网络协调器部署于汇聚节点，并假设有公共信道用于管理信息，且采集节点位置相对固定。

采集节点（文章后面部分提到的“节点”，如无特别说明，均指采集节点）周期性的通过公共信道将位置，功率，以及负载大小等信息报告给网络协调器。网络协调器将全网可用的频谱带宽采用bw表示。定义A节点集合，网络中有N个节点，ai采集节点编号，其中i=1，…，N。w（a）为节点i的频谱分配解。F={w（ai）|ai∈A}为其解的集合。采用干扰模型，即假定链路间的干扰范围已知，且为定值。

将高效频谱分配问题进行形式化描述如下：

其中，式（1）为目标函数，NUM（w（ai））表示节点ai的效用函数。约束条件式（2）中I（ai）表示与节点ai干扰范围内节点的集合，本文采用协议干扰模型，要求所有节点的干扰集合必须为空。约束条件（3）表明，所有节点分配的频谱并集必须属于整个可用频谱空间。而约束条件式（4）采用文献［9］比例公平性的定义，w'（ai）表示另外一个可行频谱分配解，只要式（3）的值小于0，则解{w'（ai）}a∈A满足比例公平性，可以证明，若效用函数采用对数函数，即log（w（ai））的形式，则可以获得约束条件（3）所需的比例公平性。比例公平性的目的是确保重载用户不会独占资源，轻载用户也不会被饿死的情况出现。

2　模型求解

遵照文献［10］中负载感知以及满足约束（4）的思路，可将频谱分配问题的目标函数设置为∑ai∈AQa·ilog（1+w（a）i）的形式，其中Qai代表采集节点ai的缓冲区队列长度。这里在log函数的自变量加1是为了在运算时确保分配解w（a）i不出现负数，且效用值不为负。该目标函数兼顾了频谱分配的效用和公平性。但是，由于节点间干扰存在，在约束（3）下求解该目标函数是一个带干扰的最大权匹配问题，该类问题是NP-难问题。为此，采用集中式着色法确保干扰用户采用不同信道，非干扰用户可以复用信道。具体实现描述如下：

算法1：集中式着色算法

（1）根据节点的位置信息和通信范围构建节点的干扰图I；

（2）在干扰图I中，将节点按照顺时针方向排序，用数组Nodes［］表示，即节点i用Nodes［i］表示，初始信道标号chn=1；

（3）针对每个节点i=1，…，N，分配给其邻居未使用的最少可用颜色，当需要更多颜色时，chn=chn+1。

经过第一部分的信道分配，可以消除干扰约束条件（2），将原问题重写如下：

从上述形式不难看出，目标函数是非线性凸函数，且决策变量的取值空间是凸集，该问题是一个凸规划问题。求解该问题常用的方法有罚函数法（外点罚函数，内点罚函数），乘子法等，前者结构简单，只需在每一步迭代时构造由原始目标函数和约束函数组成的增广目标函数，随后可以直接调用无约束优化算法的通用程序，但是算法中与障碍函数（表征各个约束）相乘的罚参数随着迭代次数增加使得增广目标函数的病态性越来越严重，对无约束优化子问题的求解带来了数值实现上的困难。乘子法则引入拉格朗日函数以及附加的适当罚函数有效地克服了该问题。

此外，在求解无约束优化问题上，牛顿法由于其不低于二阶的收敛速度被广泛应用，但是算法要求目标函数的Hess矩阵Gk=塄f（xk）在每个迭代点处正定，否则不能保证所产生的方向是目标函数在xk的下降方向，并且，牛顿法每一步迭代都需要目标函数的二阶导数，对于大规模问题其计算量较大。为此，求解无约束优化时常将其改进为拟牛顿法，其核心思想是将基本牛顿法中的Hess矩阵用某个秩1或秩2近似矩阵代替，该近似矩阵显然满足对称正定，且方向近似牛顿方向。具体算法实现伪码如下：

算法2：频谱分配算法

（1）初始化x0∈Rn，λ1∈R，σ1＞0，0≤ε＜1，谆∈（0，1），η＞1，k：=1。

（2）利用拉个朗日乘子λk将不等式约束（6）作为g（xk），构建拉格朗日增广函数

（3）求解无约束优化问题minψ（xk，λk，σk）。

%BFGS拟牛顿法

①令参数δ∈（0，1），σ∈（0，0.5），初始指定对称正定矩阵B0，使用单位矩阵In；

②计算‖塄ψ（xk）‖，若‖塄ψ（xk）‖≤ε，跳转至④，否则继续③~⑤；

③利用Bk·dk=-gk，求解dk；//dk为Armijo线性搜索方向；（9）

⑤xk+1=xk+αk·dk；（11）

其中，sk=xk+1-xk，zk=gk+1-gk。（12）

需要注意的是，Armijo线性搜索准则并不能确保zTksk＞0，所以在zTksk≤0时不考虑Bk更新；

⑦k：=k+1，跳转至②。

①如果βk≥谆·βk-1，则σk+1：=η·σk，否则σk+1：=σk；//更新惩罚因子；

②λk+1=max {0，（λk-σk+1·gi（xk）}；//更新乘子参数；（13）

③k：=k+1，跳转至1步骤。

3　仿真及结果分析

由于算法非启发式算法，且求得的结果即为最优值。为此，将算法性能与固定频谱宽度分配法以及仅考虑负载的自适应频谱宽度分配法进行横向比较。

3.1仿真数据

为验证算法的自适应性，各用户的流量强度需在不同的时间步发生变化，且速率从局部看为变速率流。NS-2提供了指数流，帕累托流，以及恒定数据流3种流量产生模式，但无变速率流量生成模块，为此，本文采取将指数流进行叠加的方式生成变速率流量。

定义1由NS-2软件按照如下规则生成的流量称为基准流量。

表1基准流量参数

由定义1可知，基准流量忙时平均时间是1 s，闲时平均时间是10 s，二者均服从指数分布，在忙时的流量速率时10 kb/s，而在闲时不产生流量。据此，可以得到一个基准流量速率统计平均的流量强度为：

按照式（14），仿真中用户基准负载强度为：

0.090 9k bit/s≈900 bit/s

定义2基准流量强度叠加的倍数称为流量强度个数。

由于各基准流量间相互独立，所以基准流量叠加产生的流量强度在统计平均意义上是基准流量强度的线性叠加。

图2不同流量强度示意图

如图2所示，0 s~199 s，200 s~399 s，400 s~599 s三个时间段分别展示了1，5，10个流量强度负载大小。

仿真总时间设置为1 200 s，认知传感器节点数为5个，按照协议干扰模型采用着色法分离出2个节点组，组内节点间通信具有干扰关系，不能复用频谱；而节点组之间无干扰关系，总频谱可以在节点组之间实现复用。分组关系如图3所示。

图3仿真节点部署

3.2仿真结果

为充分体现算法的自适应性，采用如表2所示流量强度分配方式：

表2流量强度分配表

其中，采集节点1和采集节点2在整个仿真时间内流量强度不变，分别为1和10。而采集节点3~5则每隔400 s改变一次流量强度，每个时间步总频谱数量为5 KHz。仿真实验中各参数取值为：最大迭代次数500，算法终止参数ε取10-4，罚因子σ为2.0，乘子法中的实参数η为2.0，谆为0.8，λ的初始值为0.1，Armijo线搜索参数为0.5，β的初始值为10。在每个时间步优化算法的迭代次数如表3所示。

表3每个时间步频谱分配算法的迭代次数统计

3.2.1平均吞吐率对比

下页图4展示了3种算法在不同时间步中各采集节点平均吞吐率变化曲线，从图中可以看出，所提出的频谱分配算法在不同的流量变化环境下均能有效提升系统吞吐率。与固定频谱分配法相比，本算法的平均吞吐量提升约20%~30%，最高达到50%（第11时间步）；与仅考虑队列长度的自适应频谱分配法相比，平均吞吐量提升约10%~15%，最高达到30%（第11时间步）。

图4不同时间步的吞吐率比较

3.2.2缓冲区队列长度对比

3种算法各采集节点的平均缓冲区队列长度在不同时间步的变化曲线如图5所示，本文算法在降低各采集节点缓冲区队列长度方面有明显优势。与固定频谱宽度分配法比较，采用本算法的各采集节点平均缓冲区队列长度降低了近一个数量级，与仅考虑队列长度的自适应频谱分配算法比较也有至少3倍~5倍的降低量。

图5不同时间步各用户平均缓冲区队列长度对比

4　结论

本文针对集中式认知无线传感器网络提出了一种高效的频谱分配方法。首先，按照协议干扰模型采用着色法划分干扰域，实现非干扰域之间的频谱复用，并在此基础上根据传感器采集节点负载强度进行频谱分配。仿真实验表明，该方法能够较好地适配用户负载强度的变化，并且在网络平均吞吐率以及缓冲区队列长度两个关键指标上相比固定频谱分配法和仅考虑缓冲区队列长度的频谱分配算法具有明显优势。

参考文献：

［1］AKYILDIZ I F，LEE W，VURAN M C，et al. A survey on spectrum management in cognitive radio networks［J］. IEEE Communications Magazine，2008，46（4）：40-48.

［2］VIJAY G，BDIRA A，IBNKAHLA M. Cognitive in wireless sensor networks：a perspective［J］. IEEE Sensors Journal，2011，11（3）：582-592.

［3］TIMMERS M，POLLIN S，DEJONGHE A，et al. A distributed multichannel MAC protocol for multi-hop cognitive radio networks［J］. IEEE Trans，Veh，Technol，2010，59（1）：446-459.

［4］ZAHMATI A S，HUSSIAN S，FERNANDO X . Cognitive wireless sensor networks：emerging topics and recent challenges［C］// 2009 IEEE Toronto International Conference on Science and Technology for Humanity

（TIC-STH），2009.

［5］OZGER M，AKAN O B . Event-driven spectrum-aware clustering in cognitive radio sensor networks［C］// In proceedings of the IEEE International Conference on Computer Communications（INFOCOM2013），IEEE Communication Society，2013.

［6］RAYANCHU S，SHRIVASTAVA V，BANERJEE S. Improving throughputs in enterprise wireless LANs through flexible channelization［C］// In：Proc. of the 17th ACM Int’l Conf. on Mobile Computing and Networking （MobiCom 2011），2011.

［7］CHEN J，WU J P，LI H W. SES：stable and efficient solution for rate control and spectrum allocation in wireless LANs［J］. Wireless Personal Communications，2012，66（1）：81-99.

［8］MRTY R，CHANDRA R，MOSCIBRODA T，et al. SenseLess：a database-driven white spaces network［C］// In proceedings of the IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks （DySPAN2011）. IEEE Communication Society，2011.

［9］NANDAGOPAL T，KIM T E，GAO X. Achieving MAC layer fairness in wireless packet networks［C］// In：Proc. of the 6th ACM Int’l Conf. on Mobile Computing and Networking （MobiCom 2000），New York：ACM，2000.

［10］MOSCIBRODA T，CHANDRA R，WU Y，et al. Load-aware spectrum distribution in wireless LANs［C］// In proceedings of the IEEE International Conference on Network Protocols （ICNP2008），IEEE Communication Society，2008.

欢迎订阅本刊欢迎刊登广告

An Efficient Spectrum Allocation Method for Cognitive Wireless Sensor Network

SONG Yu1，2，CHEN Jian2，WEI Li2，LIU Jiong1
（1. Xi’an Communications Institute，Xi’an 710106，China；2. Institute of Command Information Systems，PLA University of Science and Technology，Nanjing 210007，China）

Abstract：WSN widely working in ISM spectrum band is facing serious problem of spectrum scarcity，in wireless communication，Dynamic Spectrum Allocation（DSA）is considered as an important way to improve spectrum utility. In this paper，an efficient spectrum allocation algorithm based on graph coloring combining with users’load intensity for the typical centralized cognitive WSN is designed. To start with，we ensure the frequency resource fully reused among users on the geographical space. Then load intensity and fairness of users are integrated together to set a optimization model，it is solved through multiplier plus quasi-Newton algorithm structure and obtain and optimal value. Simulation experiments demonstrate that our algorithm has the remarked superiority in the system throughput and node buffer queue length（the two major optimizing objectives）when compare with the fixed spectrum allocation method and the traditional adaptive spectrum allocation algorithm.

Key words：cognitive WSN，spectrum utility，graph coloring，adaptive allocation，convex programming

作者简介：宋宇（1983-），男，陕西西安人，硕士。研究方向：无线网络。

*基金项目：国家自然科学基金资助项目（61301159，61402520）

收稿日期：2015-01-04

文章编号：1002-0640（2016）02-0013-05

中图分类号：TP393

文献标识码：A

修回日期：2015-02-24