构建连通无线传感器与执行器网络

在本节中，我们将讨论连通无线传感器和/或反应器网络的群体问题，以及如何由群体产生特定样本，目标是对网络进行仿真，并评估所提出通信协议的性能。在相关研究文献中，当需要形成无线传感器和/或执行器网络时，通常要用到连通随机UDG。通过在特定区域格局（如矩形或圆形）中配置一组节点，可以形成无线传感器与执行器网络。N个节点的位置是随机确定的（如随机选择其两个或三个坐标），且节点之间相互独立。一旦形成的拓扑通过了连通性测试（通常运行Dijk-stra的集中式最短路径算法）。预期的节点度（每个节点的平均邻居数）等于剩余节点数N-1乘以任意节点配置在节点传输区域内的概率。该概率可通过将传输区域除以总面积得到。这样，预期节点度d≈（N-1）×πr²/A，其中A为感兴趣区域的面积，r为传输半径。也就是说，。对于生成图来说，精确平均度D仅仅是图生成过程中使用的理想平均度d的一个近似值。

研究表明，当前文献在进行仿真时将传输半径r作为自变量，而对应的平均度d通常不是均匀报告的（Stojmenovic and Lin，2001a）。例如，这会导致仅报告稠密图中的仿真数据，隐藏稀疏图的传送问题。为了实现理想、准确的网络密度d，并将其作为仿真过程中的一个参数来研究从稀疏到密集的性能网络，参考文献（Stoj-menovic and Lin，2001a）提出了一种用于控制平均邻居数d的方法，它可以通过调整相应的公共传输范围R来实现。首先，N个节点是随机产生的。所有（N-1）×N/2个边按照非递减次序排列成一个表。传将输范围R设置为所有游程长度列表中第（Nd/2）个边的长度。当且仅当其欧几里得距离不大于R时，两个节点之间存在一条边。然后对形成的网络进行连通性测试。

分别将近似和精确平均度作为参数的两种网络形成算法面临着两大问题。由于稀疏网络具有较高的被分割概率，它们可能产生大量分离拓扑，在获取连通的UDG之前需要较长时间。在某些场景中，虽然假设节点位置独立是合理的，但是，一些网络可能具有不同于随机UDG的特性。例如，WSAN中的执行器节点形成自己的网络，以便于进行协同通信和提高通信与驱动性能。这对执行器相互之间的位置形成了限制。在某些应用中，新部署节点的位置可能与感兴趣区域中已部署的其他节点位置有关。例如，与会者的膝上型电脑形成一个多跳Ad Hoc网络。当新的与会者携带膝上型电脑进入会场时，最好是选择坐在其他人附近，这样网络服务才是可用的。同时，新与会者应尽量避开人群拥挤区域，以确保拥有可接受的吞吐量。

参考文献（Onat et al.，2008）对几类无线Ad Hoc网络的快速生成问题进行了研究，在这种网络中，新节点配置与其他节点的配置密切相关。该文献提出了两类算法：基于拒绝-接收和基于中心节点的算法。在基于中心节点的算法（如最小度邻近算法（Minimum Degree Proximity Algorithm，MIN-DPA））中，在配置新节点之前，先在已经配置的节点中选择一个中心节点。新节点配置在中心节点周围。在基于拒绝-接收的算法中，每一轮内为每个节点随机选择一个候选位置。然后，根据一些约束条件，对位置做出接受或拒绝的决定。(www.xing528.com)

针对节点配置存在着若干约束条件。在邻近约束条件中，新节点配置在相对于其他现有节点最近的安全距离处，且应当比一个以上现有节点近似传输半径略近些。在最大度约束条件中，如果新节点配置使得一个或多个现有节点或新节点的度超过阈值设定的最大值，则会拒绝新节点配置位置。对于传感器网络来说，覆盖约束条件是非常重要的。仅当传感器候选位置能够充分扩大整个覆盖区域时，该位置才会被接受。在实现全覆盖的极限情况下，当传感器覆盖区域没有被已配置节点完全覆盖时，该传感器候选位置将被接受。

MIN-DPA的基本思路是在中心节点周围配置新节点，中心节点在当前图中具有最小度。算法的第一步是确定半径近似值r，它可用于估计过程中的度。选择一个具有最小度的现有节点作为中心节点。新节点随机均匀地配置在中心节点（可能容易受到边界约束的影响）的传输范围内。不断重复该流程，直到配置完所有节点。最后，网络形成过程中使用的传输半径近似值r通过采用上述“边界排序”算法，由对应于理想平均度d来代替（Stojmenovic and Lin，2001a）。节点配置结束后，检查拓扑结构的连通性。仿真结果表明，采用MIN-DPA形成一个连通图，要比采用UDG要快得多，尤其是对于稀疏网络来说。

在MIN-DPA算法中，新节点位置会对已经配置的邻近节点的度产生影响。MAX-DPA（Maximum Degree Proximity Algorithm，最大度邻近算法）为网络中的所有节点增加了一个最大度约束条件。在第i轮中，节点i随机选择一个位置，当且仅当现有节点或新节点没有超过最大允许度d_max。与MIN-DPA一样，当所有节点配置结束后，调整传输半径，并进行拓扑连通性检查。