无线传感器网络中的高效多通道通信

1. 引言

作为一种新兴技术，无线传感器网络（WSNs）具有广泛的应用前景，包括环境监测、智能建筑、医疗保健以及许多其他工业和军事应用。针对MAC、路由和传输层，已提出了大量协议。然而，采用单个信道时，无线传感器网络无法提供可靠、及时且高数据率的通信由于无线电冲突和带宽有限，无法满足速率需求。例如，在大地听音项目 [Zhang et al. 2006],中，网络无法将多个音频流传输到汇聚节点。另一方面，当前的无线传感器网络硬件 （如Micaz和Telos），使用CC2420无线电模块，已经支持多个频率。因此，迫切需要在无线传感器网络中设计基于多信道的通信协议，以提高网络吞吐量并提供可靠及时的通信服务。

一些MAC层多信道协议被提出以提高无线传感器网络中的网络性能。这些协议通常为两跳邻居分配不同信道以避免潜在干扰，并设计复杂的MAC方案来协调节点间的信道切换和传输。例如，MMSN[周等人，2006a], TMMAC [Zhang et al. 2007],和MCMAC [Chen et al. 2006]就是为无线传感器网络设计的此类协议。仿真结果表明，与使用单信道的MAC协议相比，它们可以显著提高网络吞吐量。本文重点研究如何在无线传感器网络中高效利用多个信道以提升通信性能。不同于以往的工作，我们首先通过一系列实证实验探究无线传感器网络中多通道的实际特性。接着，我们提出一种用于数据采集应用的基于树的多信道协议（TMCP），并研究一个新的信道分配问题。本工作的主要贡献如下：

—本文通过大量实验对多通道现实进行了实证研究，并分析了现有多信道协议的实际问题。我们指出，由于实际中可用信道数量较少以及不可避免的时间同步误差，这些协议并不适用于通用的无线传感器网络。

—TMCP 将整个网络划分为多个子树，为每个子树分配不同信道，然后仅沿对应子树转发每个数据流。该方案在信道数量较少的情况下仍能良好运行，并且具有非常简单的传输方案，无需节点间的同步，因此适用于实际的无线传感器网络。

—我们定义并解决了一个新问题：如何将网络划分为子树以最小化树内干扰。我们证明了该问题的复杂性，并提出了一种贪心求解算法。评估结果表明，该方法在密集网络中相比其他方案显著减少了干扰。

—我们在真实测试平台上实现了 TMCP，并通过仿真和真实实验对其性能进行评估。结果表明，TMCP 能显著提高网络吞吐量，同时保持较高的数据包投递率和较低的投递延迟。此外，我们还表明其性能优于其他多信道协议。

—我们扩展了网络模型，以纳入链路质量和边的移除。提出了一种新的剪枝算法，以满足数据收集的可靠性要求。评估结果表明，在链路质量各异的网络中，剪枝过程对保持高可靠性具有重要意义。

本文的其余部分组织如下。在第2节中，我们介绍相关工作。在第3节中，我们展示来自实验的实证结果，这些实验研究了无线传感器网络中存在的多通道现实。TMCP的设计在第4节中给出。在第5节中，我们描述相关的信道分配问题，并提出一种贪心算法及其评估。在第6节中，我们通过仿真和真实实验评估TMCP的性能。在第7节中，我们提出扩展的TMCP模型。在第8节中，我们给出结论。

2. 相关工作

对于通用无线网络，已经提出了大量的多通道协议，例如多通道MAC协议 [So 和 Vaidya 2004； Li 等人 2003；Tzamaloukas 和 Garcia‐Luna‐Aceves 2001；Bahl 等人 2004]。这些协议要么要求每个节点配备多个无线收发器，要么需要某种控制消息进行信道协商。然而，它们并不适用于无线传感器网络应用。首先，每个传感器设备通常只配备一个无线收发器，无法同时在不同频率上工作。其次，无线传感器网络中的网络带宽非常有限，且数据包大小非常小。因此，信道协商数据包所产生的开销不能忽略不计。

在文献中，MMSN [周等人，2006a],、TMMAC [Zhang 等人 2007],和 MC‐MAC[Chen 等人 2006]是三种专门为无线传感器网络设计的多通道MAC协议。它们都试图为两跳邻域内的节点分配不同信道，以避免潜在干扰。我们将这些协议称为基于节点的多通道协议。仿真结果表明，与单信道协议相比，它们在无线传感器网络中的性能有所提升。然而，在基于节点的信道分配方案中，一个节点通常与其下游和上游节点使用不同信道。在多跳流中，节点必须切换信道以接收和转发数据包，这可能导致频繁的信道切换和潜在的数据包丢失。为了避免此类数据包丢失，基于节点的协议采用一些协商或调度机制来协调使用不同信道的节点之间的信道切换和传输。例如，前述三种协议均使用时隙来协调传输。这些协议在实际无线传感器网络中面临若干实际问题，包括：（1）在密集网络中信道分配需要大量正交信道；（2）节点需要精确时间同步；（3）由于频繁的信道切换，尤其是对于高数据速率流量，信道切换延迟和调度开销不可忽略；（4）这些协议通常较为复杂，对传感器节点的资源需求更高。本文通过使用Micaz节点进行实证实验，研究了这些实际问题，并表明基于节点的协议在实践中可能并不适用于无线传感器网络。因此，提出了两种不同的信道分配方法。Vedantham 等人[2006],提出了一种基于组件的协议，该协议将信道分配给无线自组织网络中的连通组件；Le 等人[2007],则提出节点基于控制理论方法动态选择信道，以实现信道间的负载均衡。尽管我们认为这些信道分配解决方案具有价值，但我们的方案侧重于如何利用多信道构建干扰较低的最优拓扑，并在实际无线传感器网络中优化吞吐量。针对这些问题，我们工作的初步版本已发表于IEEE INFOCOM 2008[Wu 等人 2008]。

最近，越来越多的研究致力于解决多通道无线传感器网络中的不同场景问题。为了降低无线传感器网络中的功耗，Xing等人[2009]和Gong等人[2010]提出了不同的策略。前者尝试在低功耗无线网络中使用部分重叠信道，后者则利用协作多输入多输出技术来提高能量效率。Luo等人[2011]将具有不同能量约束节点的最大生命周期树问题建模为半匹配问题。为了解决控制信道饱和和三重隐藏终端问题，Li等人[2010]提出采用结合占空比循环的接收端触发的MAC协议。信道分配问题还吸引了来自不同学科的研究方法。例如， Yu等人[2010]提出了信道分配问题的博弈论建模，并分析了该博弈的纳什均衡。

关于无线传感器网络中的系统和技术，已有大量文献。从应用的角度来看，如果不了 解底层无线传感器网络的特性，则无法实现特定应用目标。因此，物理环境的实际情况以及物理世界的动态特性要求应用具备高度的自适应性。Lin 等人[2006]和 Liu 等人[2014]均从连通性和维持质量的能力方面研究了不可靠网络服务。这种鲁棒性在无线传感器网络发挥着越来越重要作用的生命救援和医疗领域中往往是非常重要的[Zhou 等人 2008；Asare 等人 2012]。

3. 多信道现实实验

为了设计出优良的协议，我们需要更好地理解无线传感器网络中的多通道现实。在本节中，我们首先进行一系列实证实验，研究Micaz硬件的多通道干扰特性，包括邻道干扰以及与 802.11网络的干扰。这些特性在无线自组织网络中已有深入研究[周等人，2006b；佩特罗娃等人，2007；Mishra 等人 2006],，但在无线传感器网络中尚缺乏实证研究。随后，我们在单条路径上测量基于节点的多信道方案的性能，并研究时间同步误差的影响。通过这些实验结果，我们的分析表明，当前的基于节点的多信道方案不适用于密集且大规模的无线传感器网络，也不适用于高数据速率的应用。

3.1. 可用正交信道数量

多通道设计的一个重要参数是在无线传感器网络中实际可用的信道数量。Micaz中使用的 CC2420无线电模块[Instruments 2006]提供了16个不重叠的信道，信道间隔为5MHz。然而，并非所有信道都能在单个传感器网络中用于实现并行传输，原因是存在邻近信道干扰以及由802.11网络引起的干扰。

3.1.1. 非正交信道干扰

非正交信道干扰在通用无线网络中已得到广泛研究 [Mishra 等人 2006]。对于无线传感器网络硬件，CC2420 芯片规格 [德州仪器 2006]指出其相邻信道抑制为 45/30 dB。下文中，我们通过实验来研究其对多通道无线传感器网络性能的实际影响。

在第一个实验中，我们将三个Micaz节点排成一行，其中一个为发射器，一个为接收器，一个为干扰器。干扰器的传输与发射器同步，以产生干扰。发射器和接收器均使用信道11。当发射器改变其发射功率时，我们测量接收器在三种情况下的数据包接收率：无干扰器干扰、干扰器在信道12（邻道干扰）干扰以及在信道13（相隔2个信道）干扰。该实验结果如图1 所示。可以看出，在无干扰的情况下，当发射器的功率等级不低于3时，接收器的数据包接收率可保持在90%以上。然而，在存在邻道干扰的情况下，当发射功率等级低于7时，数据包接收率下降至50%，这明显表明邻道干扰对无线接收具有显著影响，不可忽略。在下一部分

另一方面，相隔两个信道的干扰曲线与无干扰情况下的曲线非常接近，这表明相隔两个信道的干扰影响较小。我们对其他信道进行了相同的实验，结果也类似。

为了进一步研究邻道干扰的影响，我们进行了一组新的实验，以确定接收信号强度指示（RSSI）阈值与不同信道干扰之间的关系。在这些实验中，接收器和干扰器的位置固定，相距2英尺，发射器则沿一条直线在不同位置移动。实验分两种情况进行：有邻道干扰和无邻道干扰。结果如图2(a)和2(b)所示，每个数据点代表一组RSSI值和包接收率。可以看出，在无干扰情况下，实现90%以上包接收率的RSSI阈值约为‐87dB，而在存在邻道干扰时，该阈值上升至‐77dB。当邻道干扰发生时，RSSI介于‐77dB到‐87dB之间的传输链路变得不可靠。邻道干扰的存在可能导致意外的碰撞和数据包丢失，因此在多通道协议中，安全的做法是仅使用非相邻信道。

3.1.2. 与802.11网络的干扰

另一个影响可用信道数量的因素是与802.11网络的干扰。802.15.4规范表明，一个802.11信道可能会与四个802.15.4信道发生冲突。这一问题也在 Zhou等人[2006b]和Petrova等人[2007]的研究中被探讨。在此，我们还进行了一项简单实验，以展示802.11网络如何影响无线传感器网络中的信道。我们将8对Micaz节点紧密地放置在一个存在多个802.11网络的系办公室内。每对节点使用一个唯一信道在该对内部传输数据包。所有8个信道彼此正交。我们多次运行该实验，并测量平均数据包接收率。结果如图3所示，包含每个数据集的标准差。我们可以看到，只有3个信道（11、19和25）具有良好的链路质量（接收率高于90%），而其余4个信道的链路质量较差（接收率约为60%）且不稳定（标准差较大）。该实验表明，多通道协议必须具备在少量可用信道条件下仍能良好运行的能力。否则，它们的性能在此类室内场景中可能会显著下降。

3.2. 时间同步误差的影响

另一个可能严重影响当前基于节点的协议性能的关键因素是时间同步误差。如前所述，当前的基于节点的方案需要每个节点实现精确时间同步，以协调传输

以及信道切换。然而，低功耗的Micaz节点无法提供非常高的时间精度。已知Micaz的时钟漂移为 40ppm（百万分之一），这意味着在1秒后时钟漂移可能达到 40μs。为了研究时间误差的影响，我们在Micaz节点上进行了一组实验。我们将5个Micaz节点排成一条直线，第一个节点通过逐跳方式向最后一个节点传输数据包。每个节点被分配一个唯一信道。初始时，所有节点均已同步。

首先，我们使用一种简单的基于时隙的方案作为基于节点的协议的原型。在此方案中，将10ms的时间段划分为两个时隙。在第一个时隙中，位于奇数位置的节点切换信道并向其下一个节点发送数据包，而位于偶数位置的节点保持在自己的信道上接收数据包；在第二个时隙中则相反。通过改变源端的数据速率，我们测量了以数据包接收率表示的端到端性能。完成这些实验后，我们等待10分钟，不进行重新同步的情况下重复相同的实验，并测量第二组结果，这些结果显示了存在时间误差时基于节点的协议的性能。最后，我们将所有节点修改为使用单信道，并采用标准CSMA协议来传输数据包。这些结果如图4所示。可以看出，在没有时间误差的情况下，基于节点的方案始终比单信道方案具有更高的数据包接收率。两种方案的饱和包速率（数据包接收率高于90%）分别约为90条/秒和50条/秒。另一方面，在存在时间误差的情况下，基于节点的协议的数据包接收率非常低，其饱和包速率约为10条/秒，这意味着该协议在没有同步的情况下仅能支持较低的端到端通信数据速率（约3kb/s）。该实验验证了基于节点的协议可以提升通信性能，但在存在时间误差时性能会显著下降。

错误。此外，在具有较长路径和更复杂协调方案的大型密集网络中，这种性能下降可能会被放大。研究还表明，基于节点的协议无法为高数据速率流量提供可靠且稳定的通信服务。一种可能的解决方案是定期执行时间同步操作。在这些实验中，为了保证性能，节点需要比每10分钟更频繁地进行同步。然而，无线传感器网络中的时间同步协议可能开销较大，会消耗额外的带宽和功耗，这使得频繁重新同步变得不切实际，特别是对于高数据速率应用或密集且规模较大的网络。

4. 基于树的多通道协议

每个用于无线传感器网络的多通道协议都有两个主要组成部分：信道分配和传输协调。如第3节所示，无线传感器网络的多通道现实会影响当前基于节点的多通道协议在这两个组成部分上的表现。可用的正交信道数量较少，无法满足基于节点的信道分配需求，尤其是在密集网络中。不可避免的时间误差会影响使用不同信道的节点之间的传输协调，特别是对于具有高数据速率的应用。为了在实际网络中克服这两个问题，我们认为新的多通道方案应首先采用粗粒度的信道分配策略，而不是节点级分配；其次，应通过减少信道切换以及不同信道节点之间的通信，尽量避免复杂的协调方案。

另一方面，我们还注意到传感器网络具有一种主要的流量模式，即数据收集流量，其中由传感器节点产生的多个信息流汇聚到基站。目前，大多数数据收集方案都会构建连接基站和节点的某种树结构，然后沿着该树转发数据包。然而，在单信道情况下，树内的传输冲突以及节点处的流拥塞会显著降低网络性能。

基于这些观察，我们提出了一种用于无线传感器网络中数据采集应用的基于树的多信道协议（TMCP）。使用多通道的思想是首先将整个网络划分为多个以基站为根节点的顶点不相交的子树，并为每个子树分配不同的信道，然后仅通过其对应的子树转发每条数据流，如图5所示。TMCP的优势体现在两个方面。首先，从实际考虑出发，通过粗粒度的信道分配，它所需的信道数量远少于基于节点的协议。此外，由于每条数据流都在一个子树中通过一个信道进行转发，因此我们不需要复杂的信道

协调方案，这意味着TMCP可以在无需时间同步的情况下工作。其次，从性能角度考虑，由于它在子树之间分配不同的信道，因此可以通过消除子树间干扰并利用子树间并行传输的空间复用，来提高网络吞吐量并减少数据包丢失。

TMCP 包含三个组件：信道检测（CD）、信道分配（CA）和数据通信（DC）。CD 模块用于查找当前环境中可用的正交信道。为此，使用两个传感器节点通过相互发送数据包来采样每个信道的链路质量；然后，在所有链路质量良好的信道中选择非相邻的信道。此时，我们得到 k 个信道。

给定k个正交信道，CA模块将整个网络划分为k棵子树，并为每棵子树分配一个唯一信道。这是TMCP的关键部分。划分的目标是尽可能降低潜在的干扰。可以看出，在划分之后，原始网络中的干扰可分为两类：不同树之间的干扰，称为树间干扰，通过为每棵子树分配不同的正交信道来消除；以及树内节点之间的潜在干扰，称为树内干扰。由于我们为同一子树的所有节点分配了相同的信道，因此在本方案中无法避免树内干扰，这成为主要的性能瓶颈。因此，划分的目标是将网络划分为若干子树，使得每棵子树内的树内干扰较低。在下一节中，我们将进一步研究这一问题。

分配信道后，DC组件通过每棵子树管理数据收集。当一个节点想要向基站发送信息时，它只需将其所属子树上的数据包上传即可。这里，我们假设基站配备有多个无线收发器，每个收发器工作在不同的信道上。可以看出，由于采用了基于树的信道分配策略，DC非常简单，无需时间同步。此外，基站还可以利用该网络结构执行数据分发。当基站需要发送命令或更新代码时，可以通过所有收发器发送数据包；然后，数据包将穿过每棵子树并到达网络中的所有节点。

5. 最小干扰信道分配问题

TMCP采用了一种新的基于树的信道分配方案。如前所述，该分配方案的目标是最小化树内干扰。在本节中，我们正式定义该问题，研究其复杂性，并提出一种贪心算法，通过仿真实验评估其性能。

5.1. 模型与问题定义

我们假设一个传感器网络是一个静态图 G=(V,E)，其中V是网络中所有节点的集合，E是能够在一跳范围内相互通信的两个节点之间的边的集合。这里，我们仅考虑网络中的数据收集流量。接下来，我们定义树中节点的干扰值。Burkhart 等人 [2004] 提出了基于该节点传输时可能干扰的其他节点数量的干扰值的明确的定义。换句话说，该定义将干扰视为发生在发送方而非接收器的问题。但由于干扰实际上是在接收器处发生的问题，因此我们采用以接收器为中心的干扰定义。节点 A 的干扰值是指可能干扰在 A 处接收的其他节点的数量。

定义 5.1. 节点u的干扰集应定义为 INT(u) ={v|u ∈D(v, Iv)}，其中D(v, Iv) 是以节点 v为中心、半径为 Iv 的干扰圆盘，而节点 u的干扰值定义为int(u) = | INT(u)|。

这里，我们假设当一个节点进行传输时，该发射器的干扰圆盘内的所有节点都会受到干扰。需要注意的是，这一假设在真实网络中并不总是成立，因为干扰区域并非球形，正如Zhou等人[2005],所观察到的，并且节点的干扰集可能随时间发生变化。但我们可以通过使用更大的干扰圆盘来覆盖实际的干扰区域，并为每个节点计算出保守的干扰集。我们采用干扰范围Iv而非通信范围Rv来描述干扰区域。Zhou等人[2005]指出，在真实网络中这两者是不同的。此外，我们采用了协议干扰模型[Kyasanur和Vaidya 2005],中的假设，即Iv=(1+ α) × Rv， α> 0这意味着节点u的所有邻居节点都属于INT(u)。

接下来，我们定义树的树内干扰值。这里有两个考虑因素。第一，我们应该使用最大干扰值Imax作为该树的干扰值。给定每个节点的带宽B，可以证明该树中单流容量的理论下界为B/Imax。因此，Imax决定了通过该树的单流最低数据速率，这对应用而言非常重要。第二，由于我们的干扰模型是接收器为中心的，而在数据收集流量中叶节点不是接收器，因此树的干扰是所有非叶节点中的最大干扰值。

定义 5.2. 树 T的树内干扰值定义为 int(T) =max{int(u) : u是 T 的非叶节点}.

例如，图6中的树的树内干扰值为4，尽管存在一个干扰值为5的叶节点。这里我们需要强调的是，处理非叶节点的情况并非易事。事实上，这意味着如果某个节点具有较大的干扰值，我们可以将其设置为叶节点，从而使其在数据收集流量中无需接收来自其他节点的数据包。通过这种方式，我们可以减少树中的干扰。

现在，我们可以定义划分和信道分配问题。给定k个可用的正交信道，该问题是要将一个传感器网络划分为k个顶点不相交的最小化所有树的最大树内干扰值的树，称为PMIT问题。接下来，我们研究其复杂性。

5.2. PMIT问题的复杂性

PMIT问题与图染色问题类似，但不同之处在于，PMIT问题要求具有相同颜色的节点构成一棵干扰最小的树，而图染色问题则为每种颜色寻找独立集。我们发现，与图染色问题一样，PMIT问题也是NP完全的。首先，我们将该优化问题重新表述为一个判定问题。给定一个整数d，PMIT判定问题 是判断图G是否可以划分为k棵节点不相交的树，并且每棵树的干扰值不超过d。以下定理表明该问题是NP完全的。

THEOREM 5.3. PMIT问题是 NP完全 的。

PROOF。 首先，很明显PMIT属于NP问题，因为给定一个划分，我们可以计算每棵树中每个非叶节点的干扰值，并得到每棵树的干扰值。这种验证可以通过一种直接的方式在多项式时间内完成。

接下来，我们通过将k染色问题归约为PMIT来证明PMIT问题是NP难的。给定一个图G =(V, E)和k种颜色，k染色问题是要判断能否为每个节点分配一种颜色，使得相邻节点必须具有不同的颜色。在进行归约之前，我们首先计算图G中所有顶点的最大度 。然后，我们定义一种结构 + 1‐星，其中 + 1‐星由一个作为核心的顶点和 + 1个其他顶点组成，这些顶点都与核心相邻，但彼此之间没有边相连。归约算法接收k染色问题的一个实例 作为输入。它将图G修改为一个新的图G′=(V′, E′)，具体步骤如下：首先，我们添加一个新的顶点r作为根节点，并将该根节点直接连接到G中的每一个顶点；然后，对于每条边(u v) ∈E，删除这条边，向图中添加一个新的 +1‐星，称为Suv，并将u和 v分别连接到该星的核心；最后，我们计算每个顶点的合适干扰范围，使得一个顶点的干扰圆盘仅覆盖其邻居节点，即一个顶点的干扰数等于其度。经过这些操作后，我们得到了PMIT决策问题的一个新实例 。显然，该归约可以在多项式时间内完成。图7展示了一个归约示例。在原始图中， + 1= 2。我们首先添加根节点，然后添加3个星以替换原始图中的每条边。

现在，我们证明图 G能够被k染色当且仅当PMIT问题 可以被满足。首先，假设图 G′可以被划分为

无线传感器网络中的高效多通道通信

5.2. PMIT问题的复杂性（续）

一组满足PMIT问题的树T1, T2, . . . , Tk构成的集合G。然后，我们计算一个顶点集的集合 C1, C2, . . . , Ck，其中Ci= Ti ∩V。我们断言 C是图G的一个正确的k染色。首先，显然 图G的每个顶点都包含在C中的一个集合中。其次，对于图G中的任意一条边(u v)，如果 u和 v在将G′划分后属于同一棵树T，则星形Suv也必须属于T，因为该星形仅连接u和 v。在T中，Suv的核心不是叶节点，且核心的干扰值为 + 3，因为该核心有 + 3个邻居。因此，T的干扰值至少为 + 3，这与PMIT问题的约束 相矛盾。因此，我们证明了：若图G中任意两个顶点u和 v相邻，则它们不会在G的同一棵树中，这意味着它们不在 C的同一个集合中。因此， C是图G的一个正确的k染色。

另一方面，如果图G存在一个适当的k染色 ，其中 ={C1, C2, . . . , Ck}，我们可以构造图G′中的一组树以满足PMIT问题 。首先，我们将根节点r加入到每个集合Ci中；然后，对于每一个星形Suv，由于u和 v是相邻的，它们必须位于两个不同的集合Cu和Cv中。我们任意将星形Suv放入这两个集合中的一个。假设该集合为Cu，则Cu在G′中诱导出一棵树，其中图G的原始顶点u直接连接到根节点r，且星形Suv连接到u。接下来，考虑树T的干扰值。由于u在图G中的最大度为 ，因此最多有 个星形连接到u。u的干扰数最多为 + 1，再加上 根节点。对于星形Suv的核心，其干扰数为 + 1，因为它位于一个 + 1‐星形中，并且在同一 棵树中只有u。因此，树T的干扰值最多为 + 2。于是，我们最终可以找到一组满足PMIT问题 的树。

最重要的是，我们证明了该归约是合法的。由于k‐着色问题是NP难的，因此PMIT也是NP难的。鉴于NP完全性，不存在能够在多项式时间内始终找到最优划分的精确算法。在下一节 中，我们将介绍PMIT问题的一种贪心启发式算法。

5.3. PMIT算法

在此算法中，我们假设所有节点的干扰集均已知。对于一个节点 u，令 cu 表示 u 的信道，pu 表示 u 的父节点。

该算法首先应用广度优先搜索算法来计算以基站为根的胖树。胖树具有两个重要特性：第一，节点保持其高度，并在胖树上拥有多个父节点；第二，胖树实际上是最短路径树，从基站到每个节点的分支都是跳数最少的路径，因为我们使用BFS策略来构建该树。

接下来，我们在胖树上从上到下逐层执行信道分配。在每一层中，我们总是优先处理父节点较少的节点，因为这些节点在选择信道时自由度较低。对于每个节点，我们选择一个最优信道；换句话说，我们选择一个最优树来添加该节点。选择的标准是：该树必须能连接到该节点，并且将该节点加入后对该树带来的干扰最小。如果有多个树并列最优，则选择节点数较少的树。当一个节点加入某棵树后，它会在所选树的所有可能父节点中，选择干扰值最小的节点作为其父节点。显然，该算法覆盖了图G的所有节点，并且当一个节点获得信道时，算法确保其连接到以r为根节点的树，这证明了算法的正确性。以下定理给出了该算法的时间复杂度。

THEOREM 5.4. 贪心PMIT算法的时间复杂度为O(d × k× n²)，其中d是图的直径，n是节点数量，k是信道数量。

PROOF。 构造胖树的时间复杂度为O(d × × n)，其中 是图G中的最大度。在 PMIT算法中，步骤12最坏情况下耗时O(k× n)，而从步骤11开始的循环最多运行n次。因此，repeat循环内的过程耗时O(k× n²)，且repeat循环最多迭代d次，因为树的高度从不 超过图的直径。最坏情况下的时间复杂度为O(d × k× n²)。

该算法的一个良好特性是每个节点都保持到基站的最短路径。这一特性源于该算法从上到下逐层处理胖树中的节点。因此，这种划分算法不需要额外的传输，在数据收集过程中不会降低端到端交付率，也不会增加能耗。

该算法可以很容易地修改为分布式算法，因为它只需要在每个节点进行局部搜索。首先，节点可以通过广播消息来构建胖树。在信道分配期间，节点根据来自其父节点的消息自主决策，并通知其子节点。此外，由于网络是静态的，我们可以仅在开始时或极少次数运行一次集中式算法，即使对于大型无线传感器网络也是可行的。

5.4. 贪心算法的评估

如前所述，网络划分和信道分配对于提升网络性能至关重要。在本节中，我们评估了贪心算法的性能。我们使用JAVA开发了一个图模拟器，可以随机生成图，并应用不同的方案进行信道分配。在所有实验中，我们模拟了一个200m × 200m的区域，250个节点在该区域内均匀分布，通信范围为10m∼35m，干扰范围始终为通信范围的1.5倍。由于我们是首次研究PMIT问题，目前尚无其他PMIT算法可供比较。我们采用三种替代方案作为对比：第一种是使用Prim算法构建最小生成树作为数据收集树，该方案称为单信道基础方案；第二种是我们实现了Zhou等人提出的窃听信道分配方法[2006a]，我们将其称为基于节点协议的典型方法。需要注意的是，该方案不能保证每个信道内节点之间的连通性。接着，我们找出所有节点中的最大干扰值 ρ，并使用 ρ/k作为分配k个信道后干扰值的下界。最后，我们运行贪心算法，并测量划分后所有树中的最大干扰值。在所有实验中，每个数据点均来自50次重复实验的平均结果，且对每个数据点均给出其90%置信区间。

在第一组实验中，我们使用3个信道，并通过调整通信范围来改变邻居数量。结果如图 8(a)所示。我们可以看到，贪心算法产生的干扰始终约为单信道情况下Prim算法的1/3，这表明我们的算法能够有效利用3个信道来减少干扰。与窃听算法相比，当密度较低时，窃听算法的干扰比我们的少，主要原因是它不要求保证连通性；但当密度增大时，贪心算法优于随机方案，例如当密度为18时，其干扰比窃听方案减少了17%。原因有两点：首先，当密度较大时，节点可用的信道数量不足

在两跳邻居中，窃听必须在节点间随机选择信道，导致最大干扰相对较大。而我们的算法始终尝试寻找局部最优解，从而实现更稳定的性能。其次，当密度较大时，我们的贪心算法有更多的机会将干扰较大的节点设置为叶子节点，从而进一步降低子树的干扰。最后，与下界相比，我们算法的结果接近干扰值的下界，更重要的是，该差距不会随着密度增加而扩大，这表明我们的贪心算法在不同密度下具有良好的可扩展性。

在第二次实验中，无线电范围为35米，我们改变可用信道的数量。结果如图8(b)所示。显然，在信道数量较少时，我们的PMIT算法计算出的干扰少于窃听方案；特别是当仅能使用2个信道时，我们的算法比窃听方案减少24%的干扰，比单信道减少51%的干扰。随着信道数量增加，两种方案的性能逐渐接近。当有8个信道时，窃听方案的干扰比我们的贪心算法低18%。与下界相比可以看出，在信道数量较少时，我们的算法计算出的干扰数量几乎与下界相同。

6. TMCP性能评估

TMCP在信道分配组件中使用了贪心算法。在本节中，我们通过仿真和在真实测试平台上的实验来评估TMCP的通信性能。

6.1. 仿真评估

首先，我们通过仿真实验评估TMCP的性能。我们在GloMoSim中实现了TMCP。我们采用与第5.4节仿真相同的设置，其中通信范围为10m∼40m，干扰范围始终是通信范围的1.5倍。该通信模型通常用于模拟CC2420无线电模块的射频模型。此外，在MAC层，我们使用带有ACK重传机制的CSMA，以确保大多数数据包能够被成功接收。

我们进行了三组实验。在前两组实验中，我们将TMCP与2和4个信道以及使用单信道的生成树路由协议进行了比较。首先，我们测量了不同节点密度下的网络性能。在此实验中，网络中有50个一对多的CBR流，每个CBR的速率为每秒40个数据包。结果如图9所示，每个数据点均标有90%置信区间。根据结果，TMCP在以下方面优于原始

协议。（1）通过使用复杂的网络划分和频率分配算法，具有2和4个信道的TMCP可以减少潜在的传输冲突，从而使得聚合吞吐量分别平均提高1.6倍和2.7倍，优于生成树算法。（2）通过将流量分割到不同的子树中，TMCP减少了无线电冲突以及流量拥塞，从而提高了数据包投递率并降低了延迟。（3）当节点密度增加时，TMCP表现出良好的可扩展性。例如，在图9(a)中，随着邻居数量的增加，具有4个信道的TMCP导致吞吐量持续增加，因为随着节点增多，TMCP能够更均匀地进行网络划分和信道分配，从而更好地实现并发传输的空间复用。具有2个信道的TMCP也显示出这一趋势，但当节点的邻居数量超过20个时，吞吐量不再增加，因为干扰数量超出了2个信道的承载能力。

其次，我们测量了不同网络负载下的性能。从图10可以看出，TMCP始终表现出比生成树协议更好的性能，尤其是在高负载情况下。例如，在50个CBR流的情况下，使用4个信道的TMCP实现了2.8倍的聚合吞吐量，并且投递延迟比生成树低42%。此外，在图10(b)中，生成树协议的分组投递率从95.2%下降到92.1%，而TMCP的下降幅度要小得多。这是因为TMCP将高负载分配到不同的树上，对系统负载变化的容忍度高于生成树算法。然而，我们也发现TMCP的性能不稳定。例如，在图10(b)中，当工作负载增加时，TMCP的投递率变化范围变大。这是由于这些CBR流在子树之间的分布不均，导致多个CBR流聚集的子树上可能发生流量拥塞。

最后，我们将TMCP与MMSN [周等人，2006a],这一典型的基于节点的多通道协议进行比较。在本组实验中，使用了50条CBR流，并通过将无线电范围设置为40米来使节点密度为38。如第3节所述，时间同步误差可能会影响多通道协议的性能。在此，随着信道数量的变化，我们比较了TMCP和MMSN在不同时间误差下的表现。所有结果均显示在图11中。此处，我们比较了吞吐量、投递率和能耗。总体而言，TMCP和MMSN的性能非常接近。更准确地说，当信道数量较少时，TMCP的性能略优于MMSN。例如，在图11(a)中，当信道数量少于5个时，TMCP的平均吞吐量比MMSN高出10%。但当信道数量增加时，MMSN的表现优于TMCP。这与第5.4节中的评估结果一致，即我们的信道分配算法在信道数量较少时比其他信道分配方案效果更好。此外，图11(c)显示了功耗情况

TMCP和MMSN的性能相近。然而，这里我们仅考虑数据通信的功耗。如第5.3节所述，信道分配执行得不频繁，其功耗可在时间上分摊。另一方面，时间同步误差会导致MMSN的性能显著下降，但对TMCP没有任何影响。考虑到多通道现实，TMCP比基于节点的多通道协议更适用于实际的无线传感器网络。

6.2. 在真实测试平台中的评估

除了仿真评估外，我们还在一个使用Micaz节点的真实测试平台上实现了TMCP。该测试平台由 20个Micaz节点组成；其中四个节点紧密放置，作为具有四个收发器的基站。在实验之前，我们首先使用第4节中描述的信道检测技术来寻找可用的正交信道，然后在个人计算机上运行信道分配算法。在计算出信道分配后，将结果发送到所有传感器节点。在实验过程中，选择部分节点作为源节点，向基站发送数据包。我们进行了两组实验，分别比较了使用单信道的普通生成树协议与使用2 和 4 个信道的TMCP。所有实验均重复多次并取平均值。

在第一组实验中，在改变源节点数量的同时，我们测量了数据包接收率。在此，所有源节点以每秒20个数据包的数据速率发送数据包。结果如图12(a)所示。我们看到，当源节点数量超过4个时，生成树协议的接收率较低，低于60%，而使用2个信道的TMCP可以在源节点数量达到8个之前保持较高的接收率，使用4个信道的TMCP则始终维持较高的接收率。TMCP的性能提升源于其有效减少了节点间的干扰并缓解了拥塞。

在第二组实验中，我们在网络中使用4个源节点，并改变源节点的数据速率。我们还测量了基站处的数据包接收率。结果如图12(b)所示。我们看到，对于生成树协议，源节点的饱和数据速率（接收率高于80%）为每秒20个数据包。对于使用2个信道的TMCP，饱和速率为每秒30个数据包，而使用4个信道的TMCP可支持每秒50个数据包。这些实验表明，TMCP在实际的传感器网络中表现良好。

最重要的是，我们的评估结果表明，与其他多通道协议相比，TMCP 更能适应无线传感器网络中的多通道实际情况，更适合为高密度、高数据率的无线传感器网络提供可靠、低延迟且稳健的通信，以满足关键任务应用的需求。

7. 剪枝TMCP：可靠的基于树的多通道协议

在本节中，我们介绍了基于树的多通道协议（TMCP），该协议在吞吐量、投递率和延迟方面显著提升了网络性能。TMCP 尤其在具有高流量的密集网络中优于现有协议，使其成为任务关键型无线传感器网络应用通信需求的更优解决方案。TMCP 的设计假设所有链路具有相同的质量，并且底层 MAC 协议能够提供可靠的点对点传输。然而，这一假设可能不适用于许多任务关键型应用，因为在这些应用中，网络中的链路表现出显著的链路质量异质性。Lin 等人 [2009] 观察到链路的数据包接收率存在差异，并在一个室内无线传感器网络系统中识别出两类链路（稳定和不稳定）。这种质量多样性是由信号的多径衰落以及人类和障碍物的阴影效应引起的。Sexton 等人 [2005], 在多个工业设施中测量了链路特性，这些设施包括大量金属表面和旋转机械的房间。他们的结果表明，该环境中的链路具有很宽的质量范围，并且在稳定性上存在显著变化。从所有这些观察结果可以看出，多通道协议的设计应考虑无线传感器网络中的链路多样性，并解决由劣质链路导致的潜在投递失败问题。

遗憾的是，原始的TMCP无法在存在链路多样性的情况下保证可靠的端到端传输。T MCP通过构建路由子树来最小化干扰。然而，路由树可能由低质量链路组成，从而导致投递失败。在本节中，我们重点研究如何扩展TMCP，以最小化干扰并满足端到-end可靠性要求。

7.1. 模型与可靠信道分配问题

我们在第4节的基本网络模型基础上引入链路质量度量。对于每条链路（边）e，p(e) 表示在此链路上单次尝试的成功传输概率。在实际中，该概率可通过 Fonseca 等人 [2007] 和 Woo 等人 [2003] 提出的链路估计方法获得。此外，函数 pdr(e, x) 表示进行 x 次尝试（重传）时的成功传输概率，且有 pdr(e, x) = 1 −(1 − p(e))ˣ。接下来，我们假设网络中仅存在一个基站。对于节点u，E2EPDR(u) 表示从节点u到基站的成功传输概率。假设数据包沿一条k跳路径转发，则有 E2EPDR(u) =∏ᵏᵢ₌₁ pdr(eᵢ, x)，其中 eᵢ 是该路径上的第 i 条链路。最后，我们用 RR 表示从节点到基站的最小可接受成功传输概率。给定一个 RR，通信可靠性要求为： ∀u ∈ G，E2EPDR(u) ≥ RR。

利用该模型，我们将第5节中的PMIT问题扩展为一个新的可靠信道分配问题。给定k个可用的正交信道以及可靠性

要求RR，该问题是要将一个传感器网络划分为k棵顶点不相交树，使得(1) 该划分最小化所有树中的最大树内干扰值；且(2) ∀u ∈G,E2EPDR(u) ≥RR。我们将此问题称为 RPMIT问题。作为PMIT问题的扩展，RPMIT问题也是NP完全的。

7.2. 剪枝算法

如前所述，TMCP通过构建最优的路由子树有效减少了干扰，但无法满足可靠性要求，因为子树可能包含低质量链路。为了解决此问题，我们提出了一种两步解决方案。首先，我们使用剪枝算法移除所有无法满足可靠性要求的链路，然后在剩余的胖树上运行TMCP以最小化干扰。

为了剪枝胖树，我们首先采用向下剪枝。在迭代过程中，我们首先计算父节点的 E2EPDR，然后移除那些连接到子节点但导致子节点的E2EPDR低于RR的链路。由于一个节点在胖树上可能有多条通往根节点的路径，因此出现一个问题：应使用哪一条路径的 E2EPDR来计算其子节点的E2EPDR？第一种选择是使用最小E2EPDR，这总能保证所有剩余路径满足可靠性要求。但这种过于严格的剪枝会移除实际上可用于高质量路径的链路，可能导致低层级节点无法找到路径。同时也会使剩余的胖树过于稀疏，从而减少信道分配的选择空间。相反，第二种选择是使用最大E2EPDR，仅移除质量过差、无法用于任何路径的链路。然而，这种方法不能保证所有剩余路径都符合要求。

在向下剪枝过程中，我们选择使用最大的E2EPDR。之后，我们进一步从叶节点到根节点执行向上剪枝。向上剪枝旨在移除低质量链路，以确保所有剩余路径均满足条件。我们引入一个新的节点属性——所需端到端投递率，记为RE2EPDR。对于节点u， RE2EPDR(u)定义为允许节点u的后代节点满足可靠性要求的最小端到端交付率。RE2EPDR(u)可通过以下方式计算：

RE2EPDR(u)= max v∈u’s children( RE2EPDR(v) / pdr(eᵤ,ᵥ, x)). (1)

在向上剪枝过程中，我们计算任意节点 u 的 RE2EPDR(u)，然后移除节点 u 的上行链路 eᵤ,ₚ，如果 pdr(eᵤ,ₚ,x) < RE2EPDR(u)。其中，上行链路 e 是连接 u 与其父节点 p 的链路。该向上剪枝方法保证所有剩余路径均满足可靠性要求，因为它仅保留满足所有后代节点 RE2EPDR 要求的链路。详细算法如下所示。

我们的剪枝算法具有两个良好的特性。第一，它保持了图的连通性。更具体地说，如果在原始图中存在一条连接节点 u 到根节点的合格路径，则在剪枝后，u 仍能通过一条合格路径连接到根节点。第二，该算法保证剩余网络仅由合格路径组成。这一特性源于向上剪枝，即移除所有无法满足最小可靠性要求的链路。以下定理陈述了该算法的时间复杂度。

THEOREM 7.1. 剪枝算法的时间复杂度是 O(d× × n)，其中 d 是图G的直径， 是图 G的最大度，n 是节点数量。

该剪枝算法也可以改为分布式算法，因为每个节点仅需从其邻居（父节点和子节点）收集信息。在实际部署中，我们可以首先测量网络中的链路质量，并在开始时运行剪枝算法和TMCP。在运行时期间，可以周期性地触发剪枝算法和TMCP以确保通信可靠性。

7.3. 剪枝TMCP的评估

在本节中，我们将分两个步骤评估新TMCP的性能。首先，我们通过观察其对两个网络属性的影响来分析原始和新TMCP的性能。第一个属性是可靠端到端路由的百分比，定义为在所有节点中能够到达基站的合格路由节点所占的百分比；第二个指标是潜在干扰的数量。我们使用JAVA开发了一个图模拟器，可以随机生成图，并应用不同的方案进行信道分配。在所有实验中，我们模拟一个200m × 200m的区域，250个节点在该区域内均匀分布，通信范围为10m ∼35m，干扰范围始终为通信范围的1.5倍。为了模拟实际系统中的链路多样性，我们采用Lin等人[2009],提出的链路质量模型，将链路分为劣质链路和好链路。在仿真中，一条好链路的包接收率在[0.9, 1],范围内随机选取，而劣质链路的包接收率则在[0.5、0.8]范围内随机选取。我们还假设最大重传次数为2，端到-end可靠性要求RR为80%，并且有3个可用信道可供使用。除了原始TMCP和剪枝TMCP外，我们还运行了可靠生成树算法，该算法使用Dijkstra算法计算生成树，使每个节点通过最大可靠性（权重）路径连接到基站。这种方法总能实现最高的可靠端到-end路由百分比，但无法减少潜在碰撞的数量。我们认为这是最优的单信道基于树的路由方案。在所有实验中，每个数据点均来自50次重复实验的平均结果，并为每个数据点提供其90%置信区间。

在第一组实验中，我们通过改变网络中劣质链路的比例，研究了三种方法在不同层级链路多样性下的性能。所有结果均显示在图13(a)中。当网络中的劣质链路增加时，三种算法计算出的路由可靠性均降低，但可靠生成树和剪枝

TMCP 计算出的路由比 TMCP 可靠得多。例如，当存在 30% 的劣质链路时，TMCP 仅有 42% 的节点具有可靠路由，而剪枝TMCP 能使超过 85% 的节点具有可靠路由。这种可靠性的提升源于剪枝算法移除了导致不可靠路由的劣质链路。此外，显然剪枝TMCP 的结果与可靠生成树方案几乎相同。如前所述，可靠生成树总能在存在的情况下找到一条可靠路由。该结果表明，剪枝算法剪除了足够的链路，并确保剩余网络仅由可靠路由组成。

在第二组实验中，我们通过改变邻居数量来观察三种方法在不同节点密度下的性能。这些实验中的网络包含20%的劣质链路。如图13(b)所示，两种TMCP方案相比可靠生成树方案具有明显更少的潜在干扰，这表明信道分配方案能够有效利用3个信道来减少干扰。与原始TMCP相比，这种新的剪枝TMCP具有更多的干扰。例如，在拥有10个邻居节点时，剪枝TMCP大约产生12个潜在干扰，而原始TMCP大约有10个干扰。这种性能下降是预期之中的，因为剪枝算法移除了一些链路，使网络变得更稀疏，从而减少了信道选择的选项。总体而言，剪枝TMCP以略微增加潜在干扰为代价，显著提高了端到-end可靠性，使其成为对可靠性敏感应用的更优解决方案。

作为评估的第二步，我们通过网络流量来测量剪枝TMCP的总体性能。性能指标包括吞吐量、端到-end交付率和延迟。我们在GloMoSim中实现了两种TMCP。本实验中，网络中劣质链路的比例为20%，平均邻居数量为10，可用信道数量为4。其他设置与之前的实验相同。由于关键任务应用会引发突发性流量，我们的评估重点是通过改变网络中CBR流的数量来研究不同网络负载下的性能表现。结果如图14所示。可以看出，剪枝TMCP在所有情况下均表现出优于生成树和原始TMCP的性能，尤其是在可靠性和延迟方面表现更佳。例如，在35个CBR流的情况下，剪枝TMCP相比TMCP将端到-end交付率提高了12%，延迟降低了35%。这种性能提升的原因在于，剪枝TMCP移除了劣质链路，并倾向于选择更优的链路来构建路由树，从而提高了传输成功的可能性并减少了重传次数。此外，剪枝TMCP比 TMCP对工作负载增加具有更强的容忍能力。最后，当CBR流数量增加时，这三种方案的可靠性均有所下降，延迟也随之增加

增加。然而，在所有三种方法中，剪枝TMCP的性能下降最少。

8. 结论

本文研究了如何在无线传感器网络（WSN）中高效利用多信道以提升网络性能。首先，我们通过一系列实证实验研究了无线传感器网络中的多通道现实情况。结果表明，由于可用信道数量较少以及不可避免的时间同步误差，当前的基于节点的多通道协议并不适用于真实的无线传感器网络。基于这一观察，我们提出了一种称为TMCP的基于树的多通道协议。TMCP通过将信道分配给若干棵树而非节点，能够在信道数量较少的情况下运行，并且无需时间同步。通过采用贪心算法，TMCP有效降低了潜在的无线电干扰。最后，我们在真实测试平台上实现了TMCP，并通过仿真和测试平台实验评估其性能。结果表明，T MCP能够显著提高网络吞吐量，同时在传感器网络中保持较高的数据包投递率和较低的投递延迟。此外，还提出了一种扩展方案，以在具有高链路多样性的网络中维持良好性能。