基于改进式随机不完全着色算法的无线体域网干扰协调

孙彦赞 姜玉凤 吴雅婷 马一鸣 方 勇

1 引言

无线体域网（Wireless Body Area Network,WBAN）是一种以人体为中心的短距离无线通信网络，作为无线传感网络的分支和物联网的重要组成部分，WBAN成为个人健康信息实时远程监控、采集与传输的重要技术手段之一。WBAN由一些人体表面或植入人体内的传感器节点（Wireless Sensor Node, WSN）和中心处理节点 （Central Processing Node, CPN）组成，一般形成简单的一跳星型组网结构。传感器节点将采集到的生理数据传输给中心处理节点，中心处理节点既可以对WBAN进行管理，又可以充当与外部网络之间的网关，将数据传输给远程医疗中心进行研究和分析。

WBAN最新协议标准 IEEE802.15.6规定WBAN网络节点需达到3 m的传输范围，且能够支持在633m 的空间范围内最少10个WBAN网络的部署。在如此高密度部署下的 WBAN网络容易造成用户间干扰问题。当用户间距离较近时或单位空间内人的密度高于一定值时（如商场、学校、医院等场景）会产生严重的WBAN网络间干扰，造成信干噪比（Signal to Interference plus Noise Ratio, SINR）恶化，进而降低网络吞吐量和增加网络能耗，特别当干扰造成生命关键信息丢失时，病人的生命安全将会受到严重的威胁。因此，WBAN网络间干扰抑制在增加 WBAN网络信息传输可靠性和降低系统功耗方面具有至关重要的意义[1]。

WBAN间干扰通常发生于当多个WBAN相互邻近而彼此间又没有协同时[24]-。根据WBAN分布式特点，目前比较多的干扰协调算法可分为两类：功率控制和资源管理。

传输功率控制是无线通信网络中干扰抑制的一个重要手段。文献[5～10]研究了功率控制的方法对WBAN间干扰进行抑制。其中文献[5]基于非协作博弈论提出了分布式的用户间干扰协调算法。每个体感网（Body Sensor Network, BSN）根据测量的邻近BSN的SINR，采用分布式非协作无后悔学习算法实现传感器信道和功率的自适应分配，但实现算法较复杂。文献[6]研究了 WBAN中的非协作功率控制博弈理论，在最大化总系统吞吐量的同时最小化功率的消耗。文献[7]提出基于增强学习（Reinforcement Learning, RL）算法使 WBAN对历史经验进行学习并实现 WBAN用户间分布式的功率协调。文献[8]基于人的社交预测信息，发展了基于博弈论的功率控制算法，减少 WBAN的能量消耗及用户间干扰。文献[9,10]基于简单的信道预测，提出一种基于中继（relay）传输功率控制协作通信机制，以降低传感节点发射功率和信息传输中断概率。虽然基于功率控制的方法有了一定数量的研究，但功率控制方法在很多场景下并不适用于低功耗和结构简单的WBAN传感器节点[11]。

资源分配算法是实现无线体域网用户间干扰协调的另一重要方式。文献[11～13]基于时分复用多址（Time Division Multiple Address, TDMA）的WBAN，从时隙资源分配的角度研究了WBAN间的干扰协调。文献[11]研究了WBAN传感器节点的干扰消除来最大化空间复用率，WBAN协调器通过一段时间的训练形成干扰此协调器的传感器节点列表，基于此使高干扰水平的传感节点间正交传输以避免干扰，但算法需要 WBAN协调器花费一定时间形成干扰列表，不太适用于拓扑结构快速动态变化的WBAN。文献[12]提出基于服务质量 （Quality of Service, QoS）保证的媒体接入控制（Media Access Control, MAC）层资源调度算法以避免WBAN网络间干扰，但此算法需要协调器间在调度前相互协作通信业务类型，增加了协作复杂度。文献[13]提出了一种分布式随机不完全着色算法，实现时隙资源在中心处理节点（CPN）的干扰避免分配，并提高了频谱资源的空间复用率。但由于算法对已获得着色的节点限制了其参与下一轮着色，因此该算法并没能充分提高频谱资源的空间复用率。基于此，本文提出了改进式随机不完全着色算法，可在不增加算法复杂度的前提下，进一步提升频谱资源的空间复用率。

图1 基于CPN的WBAN网络间资源调度

本文内容安排如下：第2节阐述了WBAN网络间干扰避免的资源调度；第3节给出随机不完全着色算法在 WBAN网络资源分配中的应用；第 4节提出改进式随机不完全着色算法；第5节为相关实验仿真及结果分析；第6节总结全文。

2 WBAN网络间资源调度

2.1 基于CPN的WBAN网络间资源调度

在一个单独的WBAN网络中，CPN负责管理传感器节点的接入、离开及其他功能控制，且其一般嵌入在可充电的手机或PDA设备上工作，因此本文倾向研究基于CPN的WBAN网络间资源调度，以简化传感器节点的功能，降低其能耗。基于CPN的 WBAN网络间资源调度可分两步完成：首先CPN与其邻近相互干扰的CPN协商时频资源的分配，然后 CPN再把获得的时频分配给其传感器节点，如图1所示。

2.2 着色理论的WBAN网络间资源分配

图着色理论被广泛应用于无线传感网络和认知无线电网络的干扰避免资源分配[14-16]。WBAN网络场景可建模为一个图G=（V, E），图G的顶点集V（G）表示WBAN网络CPN节点，边集E（G）表示其连接的两个顶点（即CPN节点）占用相同无线资源时会相互干扰，图G的颜色集C表示为该网络分配的不同时隙，其中|C | = k ，则WBAN间干扰避免的时隙资源调度问题可转化为对图的着色问题。通过图着色算法使相互干扰的顶点间分配不同的颜色，即相邻干扰用户间时频资源正交分配，从而实现邻近用户间的干扰抑制。

然而，WBAN用户在移动时，其拓扑结构将快速变化，用户间干扰也就会频繁变化，因此基于图着色算法的 WBAN间时频资源分配需要具有高速的收敛性。又由于WBAN协议需支持63m3的空间范围内至少10个WBAN网络，60个传感器节点的部署，因此基于图着色算法的 WBAN间时频资源分配需要实现高的信道空间复用率，以满足在时频资源有限的情况下实现 WBAN网络的高密度部署[13]。

对于一个图，当使用最少数目的颜色对图完全着色时，称之为最优空间复用着色。然而图的最优空间复用完全着色是个NP-hard问题，当前最优空间复用着色最快算法的时间复杂度仍需要O（2nnO（1））。然而当着色颜色数增加至1+Δ（G）时，则完全着色图G的时间复杂度可降低至 O （l ogn），其中 Δ（ G ）= m ax{dG（v） |v ∈ V （G）}为图G的最 大 度数，dG（v）为顶点v的度数，但此时着色算法时间复杂度的降低是以空间复用率的降低为代价的[13]。当图着色用于WBAN的资源分配时，文献[13]研究发现，当某些 WBAN用户没有业务需求时，可采用随机不完全着色算法（Random Incomplete Coloring,RIC）实现WBAN网络间的干扰避免资源调度（不完全着色即对没有业务需求的 WBAN顶点不分配颜色），既可以降低着色算法时间复杂度，又可提高颜色（时隙资源）空间复用率。

3 随机不完全着色算法

随机不完全着色（Random Incomplete Coloring,RIC）由随机值着色和不完全着色两个部分组成。其中，随机值着色目的是降低着色算法时间复杂度，提高算法收敛速度，而不完全着色是基于某些WBAN在一定时段内没有数据传输的特点，可对这些节点不着色，降低图着色所需的色数，提高着色空间复用率[13]。RIC算法流程如表1所示。

RIC算法相比传统完全着色算法可进一步提高颜色空间复用率[13]，但由于RIC算法中限制了已着色节点在下一轮着色中的颜色竞争，因此制约了颜色空间复用率的进一步提高。基于此，本文提出一种改进的随机不完全着色算法（Improved Random Incomplete Coloring, IRIC），消除对已着色节点在下一轮着色中的颜色竞争限制，以进一步提高颜色空间复用率。但此时某些节点在竞争第2种以上的颜色时，可能出现其对邻近未着色节点或分配颜色数量较少节点的可用颜色进一步占用而造成的节点着色饥饿问题。为此，所提IRIC算法中引入了公平着色影响因子ε，以在提高颜色空间复用率的前提下，保证节点间颜色分配公平性和消除节点着色饥饿问题。

表1 RIC算法流程

4 改进式随机不完全着色算法

为消除 WBAN间网络干扰的同时，进一步提高WBAN网络时频资源空间复用率和系统吞吐量，同时兼顾WBAN网络CPN资源分配的公平性，本文所提改进式随机不完全着色算法（Improved Random Incomplete Coloring, IRIC）流程如表2所示。

表2 IRIC算法流程

4.1 颜色空间复用率分析

空间复用率可以用每种颜色着色的顶点数pcV（Vertices-per-color）来表示，即

IRIC算法消除了RIC算法中只有未着色的节点才能参与下一轮颜色竞争的限制，可使已着色节点进一步参与到下一轮的颜色竞争，从而进一步提高颜色空间复用率。IRIC相对于 RIC算法空间复用率提高的一个例子如图2所示。

4.2 公平性分析

为避免某些节点在竞争第2种以上的颜色时，对邻近未着色节点或分配颜色较少节点的可用颜色进一步占用而造成的节点着色饥饿问题，IRIC算法中引入了公平着色影响因子ε, ε取整数，且ε≥0，如表2所示。当ε=0时，节点间着色可实现最大公平性，ε增大，则节点间公平性降低。如当ε=0,ℜu≥ ℜv且cv= cu时，只有|Lu（ r）|≤|Lv（ r）|时，节点u才可获得颜色 cu，而当|Lu（ r）|＞|Lv（ r）|时，意味着节点u获得的颜色数已经大于节点v所获颜色数，则不再分配 cu给节点u。通过ε的取值，可控制邻近节点间最终所分配的颜色数量差值，即可控制WBAN网络CPN节点分配时频资源的公平性。

5 仿真实验

本节对IRIC算法分别从算法时间复杂度、时频资源空间复用率、网络吞吐量和网络能耗方面进行了性能仿真。基于CPN的WBAN网络间干扰避免资源调度采用时分多址接入（Time Division Multiple Access, TDMA），信道从频域分为两条不同的信道：WBAN间信道和WBAN内信道。每条信道从时间上分为不同的时隙。CPN分别利用WBAN间信道和 WBAN内信道进行资源竞争和WBAN内传感器节点的人体生理数据收集。传感器节点仅利用WBAN内信道进行人体生理数据传输。CPN首先利用WBAN间信道通过着色算法竞争可用时隙资源，然后利用 WBAN内信道向其传感器节点发送信标以分配其所获的时隙资源。最后，传感器节点在所获得的 WBAN内信道的数据时隙向其CPN发送人体生理数据[13]。

5.1 WBAN网络场景及仿真参数

n个CPN节点随机均匀分布在 1 0×10 m2的正方形区域内，n取值 12, 25, 50, 100以分别模拟WBAN低、中、高、非常高部署密度的网络场景。CPN间干扰距离设为2 m。信道增益 hij=CPN与传感器的发射功率 p = 1 00 mW，信道带宽B= 1 2 kHz，白噪声功率谱密度 n0为-120 dBm/Hz，公平因子ε为0。着色算法时间复杂度和空间复用率分别用一次 while循环内着色轮数 Rpc（Round per circle）和每种颜色平均着色顶点数 Vpc（Vertices per color）来衡量。

5.2 仿真结果及分析

图2 RIC与IRIC颜色空间复用率分析

图3 仿真了IRIC算法与RIC算法的时间算法复杂度pcR 随可用颜色数和WBAN用户部署密度不同而变化的曲线。其中可用颜色数由1增加至15。由仿真结果可知，RIC算法随着可用颜色数的增加，其执行一次着色循环的着色轮数基本没有变化，这是由于RIC算法在对顶点着色过程中，顶点获得一种颜色即退出着色循环，顶点没有可用颜色时也立即退出着色循环，颜色数大小对着色循环次数影响很小。随着 WBAN网络部署密度n的增加，CPN间干扰机会增大，因此RIC算法pcR 会有所增加。而在本文所提IRIC算法中，当顶点获得颜色后，顶点为进一步提高颜色复用率，并不会立即退出着色循环，而是直到其可用颜色集为空集时才退出着色循环，因此，随着可用颜色数的增加，其pcR 呈递增趋势。随着WBAN网络部署密度n的增加，CPN间干扰机会增大，这样一方面会造成IRIC算法每次着色循环内着色轮数pcR 有所增加，另一方面又会使每个顶点的可用颜色集的颜色数降低，从而造成每个顶点着色轮数pcR 的减少，最终第 2种影响因素超过了第 1种影响因素，从而造成随着 WBAN网络部署密度n的增加，pcR 呈减少趋势。

IRIC算法与 RIC算法空间复用率对比仿真如图4所示。在一定的WBAN网络部署密度下，对RIC算法，CPN节点分配一种颜色后会立即退出着色循环，随着颜色数的增加，每种颜色可着色的顶点数减少，甚至会出现某些颜色没有顶点可着色的情况，因此其颜色复用率随可用颜色数的增加呈递减趋势。随着 WBAN部署密度的增加，节点对颜色的需求量会上升，因此其颜色复用率会有所上升。对本文所提IRIC算法，由于CPN节点在获得一种颜色后并不会退出着色循环，直到其可用颜色集为空时，CPN节点才会退出着色循环。因此，对每种颜色来说，其着色地位是相同的，因此每种颜色空间复用率是一定值，颜色数的增加不会降低颜色的空间复用率。而随着WBAN网络部署密度的增加，每种颜色可着色的顶点数会上升，意味着每种颜色空间复用率的提升，因此所有颜色空间复用率的期望值也就上升。

图5是IRIC算法与RIC算法的用户平均功率随 WBAN网络部署密度和可用颜色数不同而变化的仿真对比曲线。平均功率为

其中 nk为颜色（时隙）k时工作的CPN数量，K为可用颜色数量，P为CPN或传感节点发射功率。 由图5可知，对RIC算法，随着可用颜色数量的增加，每种颜色的平均着色点数降低，意味着每时隙工作的节点数 nk减少，因此在WBAN部署密度n一定时，用户的平均功率随着可用颜色数的增加而降低。而对IRIC算法，随着可用颜色的增加，其每种颜色的平均着色点数基本不变，意味着每时隙工作的节点数 nk基本不变，因此在WBAN部署密度n一定时，用户的平均功率随着可用颜色数的增加基本保持不变。当用户密度n增加时，由图5仿真可知，nk增加的幅度远小于n增加的幅度，因此，对RIC和IRIC算法，随着WBAN部署密度的增加，用户平均功率减少。

图3 IRIC算法与RIC算法时间复杂度 pcR 仿真对比

图4 IRIC算法与RIC算法颜色 空间复用率 pcV 仿真对比

图5 IRIC算法与RIC算法 用户平均功率仿真对比

IRIC算法和 RIC算法系统总吞吐量的仿真对比如图6所示。在WBAN部署密度一定时，随着可用颜色的增加，RIC算法空间复用率降低，因此，其系统吞吐量呈下降趋势；而IRIC算法可保持空间复用率在较高的稳定值，因此系统吞吐量保持恒定。当WBAN部署密度变大时，RIC和IRIC空间复用率上升，因此系统吞吐量都呈上升趋势。

图6 IRIC算法与RIC算法系统总吞吐量仿真对比

6 结束语

本文提出了一种改进式随机不完全着色算法（IRIC），实现了WBAN网络间干扰避免的时隙资源分配。该算法在兼顾用户公平的前提下，提高了资源分配空间复用率，优化了系统吞吐量。仿真结果表明，所提IRIC算法相比RIC算法时间复杂度略有恶化，但该算法有效地改善了资源空间复用率和系统吞吐量。未来会进一步研究公平因子ε对网络总吞吐量和WBAN网络间公平性的影响。

[1] Movassaghi S, Abolhasan M, Lipman J, et al..Wireless body area networks: A survey[J]. IEEE Journal on Communications Surveys & Tutorials, 2014, 16（3）: 1658-1686.

[2] Yang Wen-bin and Sayrafian-Pour K. Interference mitigation for body area networks[C]. IEEE Conference on 22nd International Symposium on Personal Indoor and Mobile Radio Communications （PIMRC）, Toronto, 2011: 2193-2197.

[3] De Silva B, Natarajan A, and Motani M. Inter-user interference in body sensor networks: preliminary investigation and an infrastructure based solution[C]. IEEE Conference on Sixth International Workshop on Wearable and Implantable Body Sensor Networks, Berkeley, 2009:35-40.

[4] Dong J and Smith D. Cooperative body-areacommunications: enhancing coexistence without coordination between networks[C]. IEEE Conference on 23rd International Symposium on Personal Indoor and Mobile Radio Communication （PIMRC）, Sydney, 2012: 2269-2274.

[5] Fang Geng-fa, Dutkiewicz E, Yu Ke-gen, et al.. Distributed internetwork interference coordination for wireless body area networks[C]. IEEE Conference on Global Telecommunications Conference （GLOBECOM 2010）, Miami, 2010: 1-5.

[6] Kazemi R, Vesilo R, Dutkiewicz E, et al.. Inter-network interference mitigation in wireless body area networks using power control games[C]. IEEE Conference on International Symposium on Communications and Information Technologies（ISCIT）, Tokyo, 2010: 81-86.

[7] Kazemi R, Vesilo R, Dutkiewicz E, et al.. Reinforcement learning in power control games for internet work interference mitigation in wireless body area networks[C]. IEEE Conference on International Symposium on Communications and Information Technologies （ISCIT）, Australia, 2012:256-262.

[8] Zhang Zhao-yang, Wang Hong-gang, Wang Chong-gang, et al.. Interference mitigation for cyber-physical wireless body area network system using social networks[J]. IEEE Transactions on Emerging Topics in Computing, 2013, 1（1）:121-132.

[9] Dong Jie and Smith D. Joint relay selection and transmit power control for wireless body area networks coexistence[C].IEEE International Conference on Communications （ICC）,Australia, 2014: 5676-5681.

[10] Dong Jie and Smith D. Opportunistic relaying in wireless body area networks: Coexistence performance[C]. IEEE International Conference on Communications （ICC）,Hungary, 2013: 5613-5618.

[11] Movassaghi S, Abolhasan M, and Smith D. Smart spectrum allocation for interference mitigation in Wireless Body Area Networks[C]. IEEE International Conference on Communications （ICC）, Australia, 2014: 5688-5693.

[12] Jamthe A, Mishra A, and Agrawal D P. Scheduling schemes for interference suppression in healthcare sensor networks[C].IEEE International Conference on Communications （ICC）,Australia, 2014: 391-396.

[13] Cheng Shih-heng and Huang Ching-yao. Coloring-based inter-WBAN scheduling for mobile wireless body area networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24（2）: 250-259.

[14] Gandham S, Dawande M, and Prakash R. Link Scheduling in wireless sensor networks: distributed edge-coloring revisited[C]. IEEE Conference on 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Miami, USA, 2005, 4: 2492-2501.

[15] Fonseca Jr B J B. An augmented graph-based coloring scheme to derive upper bounds for the performance of distributed schedulers in CSMA-based mobile Ad Hoc networks[C]. IEEE Conference on Wireless Communication and Mobile Computing, Wuhan, 2006: 761-766.

[16] Sun Yan-zan, Hu Hong-lin, Liu Fu-qiang, et al.. Dynamic spectrum access based on MAC-layer spectrum sensing and prior channel pre-allocation strategy[J]. IEICE Transactions on Communications, 2010, E93-B（3）: 609-619.