采用有效的多信道资源分配算法可以增强网络的稳定性, 提高网络的通信效率.因此提出一种适用于大规模网络的资源分配算法, 既可用于静态网络, 也可用于动态网络.首先根据路由树的关系, 依据提出的时隙复用规则, 给出节点间的时隙分配.仿真与管载数据包算法比较, 在不同的通信距离下, 网络的吞吐率分别提高35.7%和18.4%.在动态网络中, 恢复网络通信产生的通信量与节点个数的变化有关, 与总通信量的比例要小于网络节点变化的比例.
Using multi-channel resource assignment increases the stability of wireless network and throughput. A resource assignment algorithm is proposed for static and dynamic large scale wireless sensor networks. According the policy to reusing link, links are assigned to nodes based on routing information. In the simulations, it improves the throughput by 35.7% and 18.4% in different communication ranges compared to packets in pipe (PIP). In dynamic networks, network traffic generated to restore traffic is related to the number of nodes. The proportion of new traffic to total traffic for networking is less than the proportion of network nodes change.
无线传感器网络在工厂监控、环境监测、建筑物监测中发挥了越来越重要的作用[1-2].由于节点的成本较低，易于安装，网络通常通过增加监控密度以达到更准确的监控要求，这使得网络的规模越来越大，需要使用相应的资源分配算法保证大规模网络中无线传感器节点的正常工作.在无线通信环境中，网络的链路是不可靠的[3]，无线节点可能会被移动或者电量耗尽，所以网络的拓扑并不是一成不变的，可能有新的节点加入，或者已入网的节点离开[4]，因而资源分配算法应具有一定的拓扑适应性.且在保证网络性能的同时，采用尽量少的网络中的无线通信传输来及时恢复网络通信. Gabale提出管载数据包(PIP，packets in pipe)算法适用于多跳多信道的网络，并可以拓展到树状网络[5].前期的工作[6]以集中式分配为主，提出了资源分配算法适用于工业无线应用的需求.笔者提出多信道多跳的算法(MCMH, multi-channel multi-hop)是基于时分多址(TDMA, time division multiple access)，它不需要进行冲突监测，并且节点是在需要传输的时候才进入到发送状态或者接收状态，其他的时间段可以进入休眠状态，以延长节点的生命周期.另外，对网络拓扑的动态变化进行了详细的分析和仿真.
1 资源分配问题描述针对无线传感器网络的传输特点，采用TDMA传输调度方式避免冲突.无线网络的通信资源主要是信道和时隙. IEEE802.15.4可采用16个信道，应充分利用信道和时隙对网络中的节点进行调度，降低传输的延迟.由于无线传感器网络部署支持多跳的网络拓扑，并且多跳可以简单地转换为单跳网络.因此本文讨论的是多跳多信道网络的资源分配问题.
假设以下条件成立：
1) 节点的位置信息是已知的、固定的，配备的是全向天线.
2) 每一个节点在同一时间最多只能成功接收一个传播的信息.但是，当节点具有多个信道接收的能力时，可以扩展为接收多个传播的信息.
3) 不保证每一个节点可以直接与汇聚节点进行通信.
4) 网络中的节点除汇聚节点以外，都采集数据，即每个节点在一定的时间周期内都有数据包发送.
5) 时隙的长度根据规定的最长数据包决定，是可调的.连续的时隙集合组成的周期，成为帧结构.
6) 节点传播是按照分配好的调度来进行的.一个节点只能在给定的时隙内采用分配好的信道发送数据或者接收数据.
资源分配的目的是达到最短时隙周期，完成上行链路和下行链路的通信，并且使得网络中的节点的通信没有冲突.
2 MCMH算法实现及分析2.1 算法描述算法需解决网络时隙和信道二维资源分配调度问题，并提高吞吐率.算法需要对于网络中存在的上行和下行的每一条链路l(a, b)分配时隙和信道资源，a为发送节点，b为接收节点.因此对于每个节点在时间t给出ft (u, v, c)=1和ft(v, u, c)=1的集合，∀v∈V, t≤T, ∀c∈C, 其中T是最长周期.算法的目标是最小化T，实现全网的资源分配.
由于数据包的发送来源和时间要求的不同，把时隙分配分为2个阶段：下行方向的分配和上行方向的分配.下行方向的分配从网关节点开始，上行方向的分配从叶子节点开始.需要注意的是，当复用其他节点的时隙时，只选择其中不违背冲突原则的部分进行复用.如果复用规则都不满足时，需要重新分配一个新的时隙.
1) 下行方向的分配
下行方向的分配从根节点到叶子节点，根节点需要传输信息到所有的孩子节点.假设每个节点有1个包要传输，且每个包都能在1个时隙之内传输结束，因此至少需要给节点分配与孩子节点个数相等的时隙.采用贪心策略分配的最大的值不超过图最大的度加1，即小于max{min{d(xi)+1, i}}，其中d(xi)是冲突图中最大的度，i为节点的编号.下行复用的规则是判断如果有祖父节点，则可以复用祖父节点的时隙，或是祖父点的同级节点的时隙.另外，节点可以复用兄弟节点的时隙.
2) 上行方向的分配
上行方向的分配从叶子节点开始.每个节点需要传输数据到它的父节点.假设每个节点有1个包要传输，且每个包都能在1个时隙之内传输结束，因此每个节点需要的时隙数应该等于它的所有子孙节点加上自己的数据包所需要的时隙.上行复用的原则是先判断如果孙子节点存在，可以首先复用孙子节点的时隙，其次复用兄弟节点的孩子节点的时隙.
2.2算法复杂度分析
假设网络的路由树最大有m+1级，每个节点有最多N个子节点，m+1级的节点没有子节点.
下行时隙分配的最大的数量是由网络最大的子节点的数量决定的.最大的子节点的个数为N，所需的最大的下行时隙的分配是O(2n).
对于上行方向的分配，假设每个节点以一定的周期产生数据包，为了避免网络拥塞，采用通信胖树对时隙进行分配.因此分配先从m+1级叶子节点开始，同父节点的m+1级的节点的最大个数为n，因此最多需要分配n个时隙. m+1级的其他节点可以复用n个时隙. m级节点不仅需要完成自己数据向m-1级节点的发送，同时还需要转发m+1级节点的数据.同父节点的m级的节点的个数最大为n，因此m级最多需要O(n×(n+1))个时隙.由此类推，到1级节点所需要的新的时隙个数为O(nm).上行网络中所增加的新的时隙的个数为
|
(1) |
一个新的节点加入网络，对上行方向而言，全网总的时隙增加的个数小于等于1.新加入的节点的上行方向中，从新加入的节点到网关汇聚节点方向上的点都需要增加一条新的链路的时隙分配.不妨设新增的节点为u，加入成功以后在路由树的第hu层.
观察1 假设新增节点增加的通信量最少为上行
节点在第hu层，对于上行链路而言，从新增节点到网关节点之间路由边都需要增加一条链路，新增的通信开销与节点所在的层数有关.如果是下行链路，需要建立新增节点和父节点之间的通信.新增节点增加接收链路，父节点增加发送链路.
如果要离开节点v有孩子节点，即M≠∅.假设该v有同父同级节点k，M内的所有节点和节点k的距离小于通信距离，则节点v离开后，其所有的子节点全部成为k节点的节点，如图 1(a)所示.当不是全部的节点能够平移给k节点时，某些节点要调整路由树的级别，如图 1(b)所示.
|
图 1 节点离开两种情况分析 |
观察2 如果离开节点的子节点能平移给同级节点，则总的通信量的下行方向为
观察3 如果离开节点的子节点的不能平移给同级节点，则仍然在网子节点作为其他子节点的中继节点.如果子节点中拥有最小路由层数的节点p仍然在网络，那么其他的子节点以p为父节点，从而调整了路由树的级别.
3 实验测试及分析3.1 固定网络测试假设区域面积为300 m×300 m，节点个数从100增加(递增)到260.在相同参数的情况下，取实验模拟100次的平均值.
将MCMH方法和PIP方法进行比较. R表示两个节点间最大通信距离.假设每个数据包长度是256 byte，每个时隙的长度是1 ms.得到的网络吞吐率如图 2所示，X轴表示的是节点个数，Y轴是吞吐率.当节点个数增加时，复用时隙节点个数也相应地增加，因此网络的吞吐率增加.
|
图 2 网络吞吐率均衡态与非均衡态域内负载比较 |
当节点个数为180，R=40时，吞吐率下降.原因是通信距离增加时，干扰的范围也增加.节点密度达到某个值时，网络中可并行的节点数量达到最大值，随着节点密度再增大，而可并行的节点通信的数量是有限的，因此吞吐率保持平稳或者略微的下降. R=35，MCMH的吞吐率提高了35.7%，R=40，MCMH的吞吐率平均提高18.4%.
3.2 动态网络测试首先讨论节点增加的情况，为了不使网络整体产生大的变化，不妨假设新的节点只是成为叶子节点，并不成为其他已入网节点的路由或中继.新增的节点首先进行信道扫描，并选择路由树级别低的节点作为自己的父节点.初始网络的节点个数从100到260，节点从2%增加(递增)到20%.每种参数状态下模拟100次取平均值. 图 3给出节点增加带来的通信量，也就是节点配置相应的链路带来的通信量.其中，X轴表示节点个数变化的百分比，Y轴表示原先网络中的节点数目，Z轴表示产生的通信量.随着节点个数的增加，增加节点个数的比例增加，修复网络的通信量随之增加.
|
图 3 网络节点增加通信量的影响 |
为了能够直观地比较通信量变化和配置初始网络的通信量的关系，图 4给出修复网络的通信量和原先网络形成产生的通信量的比值，X轴表示变化的百分比，Y轴表示原先网络中的节点数目，Z轴表示占原先网络通信量的百分比.从图 4中可以看出，新增节点后，修复网络通信产生的通信量所占初始网络配置的通信量的比值略小于节点个数增加比例，平均比值为节点增加比例的84.81%.
|
图 4 网络增加通信量占网络形成通信量的百分比 |
其次讨论节点离开的情况，如果节点是叶子节点，离开比较容易；如果节点是中继节点，那么就会出现图 1中的两种情况.初始网络节点个数固定, 节点减少的比例增加，减少节点个数增加，调整网络的通信量也增加.节点减少调整的通信量大于节点增加调整的信息量，虽然只是在局部内进行调整，但是需要中间节点进行数据包的转发.
初始网络节点的个数从100~260.节点减少个数占已入网节点个数的比例从2%~20%递增. 图 5给出由于节点离开产生的通信量.随着节点个数的减少，离开的节点是中继节点的概率也增加，修复网络的通信量随之增加.
|
图 5 网络节点离开通信量的影响 |
图 6给出修复网络的通信量和原先网络形成产生的通信量的比值，所占比例约等于节点数变化的比例.减少节点后，修复网络通信产生的通信量所占初始网络配置的通信量的比值近似等于节点个数减少比例.
|
图 6 网络增加通信量占网络形成通信量的百分比 |
提出了一种基于路由树的资源分配算法.分别给出上行链路分配和下行链路分配的方法，并依据冲突图染色的方法完成信道分配.利用时隙复用及多信道的策略，充分提高了网络的吞吐率.算法具有多跳连接、TDMA传输、多信道、扩展性和集中控制的特点.尽管笔者针对射频个数为1的传感器网络进行分析，但是算法可以很容易地扩展到多射频的传感器网络中，例如射频采用(MIMO，multi-input multi-output)的节点.
和PIP方法进行了仿真比较，MCMH算法在网络吞吐率上有所提高.由于无线链路的不稳定性，使得网络的拓扑是动态变化的.笔者在对网络进行通信恢复的同时，尽可能地减少了对网络中已存在的节点通信链路的调整.仿真结果表明，当网络拓扑发生变化以后，调整分配结果的通信开销和节点变化个数有关.节点增加全网的吞吐率会增加，节点离开全网的吞吐率会减少.
| [1] | Akyildiz F, Su W, Sankarasubramaniam Y, et al. A survey on sensor networks[J].Communications Magazine, IEEE, 2002, 40(8): 102–114. doi: 10.1109/MCOM.2002.1024422 |
| [2] | Yang Y, Zhang X, Li W, et al. Profiling threat-based area by mobile wireless sensor network coverage[J].Journal of Computational Information Systems 8, 2012(24): 10177–10185. |
| [3] | Wan Y, Li L, He J, et al. Anshan: wireless sensor networks for equipment fault diagnosis in the process industry[J].Sensor, Mesh and Ad Hoc Communications and Networks, 2008: 314–322. |
| [4] | Zuniga M, Krishnamachari B. An analysis of unreliability and asymmetry in low-power wireless links[J].ACM Trans, Sensor Networks, 2007, 3(2): 7. doi: 10.1145/1240226 |
| [5] | Yang Y, Zhang X, Luo Q, et al. Dynamic time division multiple access algorithm for industrial wireless hierarchical sensor networks[J].China Communication, 2013, 10(5): 137–145. doi: 10.1109/CC.2013.6520946 |
| [6] | Gabale V, Chebrolu K, Raman B, et al. PIP: a multichannel, TDMA-based MAC for efficient and scalable bulk transfer in sensor networks[J].ACM, Transactions on Sensor Networks, 2012: 28. |