0 引言

    网络中传感器的数目过多，会使网络间通信产生更多的能耗，集中式算法易导致单个节点失效^[1-2]。因此，无线传感器网络(Wireless Sensor Network，WSN)^[3-4]协议必须含有分布式定位功能。文献[5]利用自组织方式确保连通性并对网络进行重新配置，应用于网络层或节点层。然而，每个节点都包含在自组织网络中时，无法保证其能量效率^[6]。

    本文提出一种WSN能效优化的自组织位置感知协议(Energy Efficient Self-organized Location aware Protocol，EESLP)，根据拓扑控制进行自组织处理，综合考虑两个WSN参数：数据包投递率和能耗，在增加数据包传输率的同时降低了能耗。

1 提出的自组织位置感知协议

    本文协议分四个步骤进行路由选择，工作流程如图1所示。

1.1 位置感知结构的构建

    图2所示为基于位置感知构建的树结构，其中，黑色节点表示Sink节点（根节点），灰色节点表示锚主干节点，白色节点表示叶节点。位置感知结构构建算法如算法1所示。

    算法1：位置感知结构构建算法

    输入：含有V个顶点(V←v₁，v₂，…，v_n)和E条边的非连通图G。

    输出：通过锚节点进行完全连接的树结构。

    (1)在图G选取根顶点V_R，即V_R∈G。//V_R是Sink节点

    (2)添加连接V_R和v_i以及节点v_i和v_j的边e_i。//i，j=1，2，3…

    (3)若v_i和v_j是V_R的两跳距离节点，则执行步骤(4)

    (4)检测C(连通性)。//利用G图中的两个未连接邻居节点将v_i和v_j连接

    (5)选取v_abi和v_abj作为第一层主干锚节点，命名为V_ab1和V_ab2。//V_ab表示主干锚节点

    (6)持续步骤(3)～(5)，直到图G中的所有节点都连接

    (7)通过V_abi和V_abj将位置信息告知V_R

    (8)否则

    (9)运行步骤(2)

    (10)结束

1.2 用于结构维护的拓扑控制

    利用拓扑控制维护结构贯穿整个过程，通常通过减少或简化网络的拓扑结构来进行节能，同时维持网络的一些重要特性（如连通性和覆盖范围等）^[7]。拓扑控制和维护算法如算法2描述。

    算法2：拓扑控制和结构维护算法

    输入：含有V个顶点(V←v₁，v₂，…，v_n)和E条边的未连接图G。

    输出：通过锚节点进行完全连接的树结构。

    阶段一：利用拓扑控制进行拓扑结构简化（连通性和覆盖范围）

    (1)当V中节点v（叶节点）的能量减少或改变位置时。//节点能量耗尽或节点处于运动过程中

    (2)v_ai←v_i。状态的改变指向锚主干

    (3)v_i←v_abi←V_R。//连通维护层级V_R，v_bi和v，其中v与新锚点v_bi连接

    (4)若v_bi的一跳邻居节点中含有一跳未连接的路径，将v_bi添加到v_b上

    (5)更新G中所有的由v_i到v_abi的连接

    (6)树(T)结构维护

    阶段二：拓扑结构维护阶段。

    (7)使G含有v_i，v_ab和V_R

    (8)若P(v_i≠v_ab≠V_R)能量不等

    (9)则从G移出v_i，当需要时恢复v_i

    (10)在G中利用V_R维护树结构

1.3 节能机制

    利用位置模型对网络进行建模，将网络拓扑作为构建结构的关键参数，能量效率如图3所示，负载均衡算法如算法3所示。

    算法3：负载平衡算法

    输入：无向图G=(V，E)。//V，E分别表示顶点和边的集合。

    输出：一个连接网格结构L表示图G的子集。

    (1)构建局部网格结构l_n←{V，E}。//在其覆盖区域内至少含有2个未连接的邻居节点

    (2)在l_n∈L中构建1个一维的网格集合

    (3)L(v)∈{G}，这里L≥2，3，4，…。//v表示一个顶点

    (4)在集合L中寻找一个子集合A用于更替路由，如l₁，l₂，…，l_n∈V

    (5)若l₁，l₂为更替路由虚拟节点。//节点度l₁，l₂≥1或2

    (6)则将叶节点n与L或l连接

    (7)向局部网络添加节点L_n←L∪l∪n

    (8)当L(v)改变其位置时。//v，u是L(局部结构)中的顶点

    (9)l(u)←L(v)。//通过′l′维护连接′L′，l是L的子集

    (10)只有当l一跳连接u和v，则增加v，u

    (11)类似的，添加一跳l₁，l₂，…，l_n到L的其他节点

    (12)(l，n)←更新i。//i为信息状态

    (13)若l₁在一跳中不可利用或不在传输范围内。//仅用于较小传输范围

    (14)n←l。//叶节点(n)变成虚拟节点

1.4 自组织

    利用自组织方式^[8]降低节点或网络中的消息复杂度，为避免碰撞、竞争和连接失败等问题，通过重建和位置结构的拓扑过程获得自组织，利用分布式定位算法实现位置结构的拓扑过程。若一个节点希望进入任何一个工作区域，则会对它的服务进行分层限制，并产生支持每个节点的平面路由。在真实的数据传输过程中（如网络电话），仅有平面路由是不行的。与此同时，在一个分层系统中，将实时传输设置为高优先级，并将节点连接到低拥堵的区域。为了减少路由和控制开销，允许中间节点或中继节点处理其他节点的拥堵情况。自组织算法如算法4所示。

    算法4：EESLP中的自组织算法

    (1)算法在G中的每个WSN上执行；L∈G，L为位置结构

    (2)用i表示整数，w，r∈W_i；//W_i为位置结构节点集合，w为W_i中元素，r为中继节点

    (3)执行自私行为，调整节点到其最初的位置或维护路由进程

    (4)if将w_i变为w_i+1 or将r_i变为r_i+1，then

    (5)在G中寻找所有可能执行自私行为的自组织节点

    (6)if w=w(i)，then

    (7) if ′i′是奇数，then w支撑奇数连接（最小度）

    (8) else if ′i′为偶数，将连接调整到i+1个r_i节点

    (9) end

    (10)else 为连通性选取新的wi

    (11)end

2 实验

    在移动场景和稳定场景下对本文协议进行了仿真实验和分析。

2.1 实验设置

    仿真中，接收功率设置为0.1 W，传输功率设置为0.281 4 W。利用NS2仿真器构建含有200个节点、大小为1 000 m×1 000 m的WSN区域，闻讯间隔为0.90 s，采用随机位点模型。所有节点的初始能量为0.25 J，节点的传输范围为10 m～50 m，仿真持续时间为120 s。在第一种场景中，所有节点都是固定的，并且按序生成10个UDP会话，每个会话传输50个恒定比特率（CBR）数据包。在初始阶段，所有节点都是黑色的，拥有红色节点的度为5；用黄色表示运动节点。在移动体系结构中，设置节点的移动速率为1 m/s。利用稳定能效自组织位置感知协议(Stable Energy Efficient Self-organized Location aware Protocol，SEESLP)表示稳定性分析，移动能效自组织位置感知协议(Mobile Energy Efficient Self-organized Location aware Protocol，MEESLP)表示移动场景分析，另外，每个场景下设置2种覆盖区域范围，I和II分别表示25 m和50 m的覆盖区域。

2.2 结果分析

    由于网络是利用标记策略形成，因此作为关键因素的位置路由成为性能比较的重点。在相同的参数设置下，随机生成10个连接的UDGs，计算每个图的LS以及平均LS尺寸，LS表示位置结构中用于维护连通性所需的节点个数，结果如图4所示。由图4可知，SEESLP-II策略仅需要8%的节点去维护连通性。根据邻近Sink节点识别机制，位置结构中仅需12个节点连接Sink节点与源节点。另一方面，MEESLP-I需要25%的节点进行移动维护，这是因为在移动场景下，具有高的节点密度和节点移动性，节点之间需要交换更多的控制负载。同时还可以看出，若网络是稀疏的，网络中的大多数节点将会被一个位置结构包含，这与高或低的节点度策略无关。若网络变得稠密，利用高节点度减小EESLP的尺寸。因此，最高节点度策略优于最小节点度策略。

    传输范围分析是基于不同传输范围内所需的中间节点的个数。不同场景下，传输范围在10 m～50 m内变化时，控制节点个数，结果如图5所示。可以看出，SEESLP中，当传输范围为10 m时，连通性仅需30个控制节点，随着传输范围的增加，所需的控制节点个数相应减少，当传输范围为50 m时，相应的控制节点个数为11。由于结构的位置性，MEESLP需要近50%的节点维护连通性。此外，随着传输范围由40 m增加到50 m，两种方法的LS尺寸都减少，随着传输范围的进一步增加，这两种方法的尺寸会越来越接近。

    平均节点度分析中，评估了节能方法的可扩展性，如图6所示，网络的密度限制为200个节点。从图中可知，SEESLP-II仅需4个中继节点。由于当一个支配者的节点级别增加，它就不能连接所有的节点，因此与传输范围分析相比，节点级别分析需要更大量的中间节点。

    图7显示了数据包投递率的比较。一个数据包的大小在16 bit到128 bit之间变化，利用本文协议传输数据包并对包投递率进行分析。在WSN网络中存在3种会影响PDR的情况：（1）节点发送功率变化；（2）节点数量变化；（3）网络大小变化。

2.3 性能比较

    将本文协议与文献[5]、文献[7]和文献[8]提出的协议进行比较，结果如图7(a)所示。从图中可以看出，本文协议具有最优的数据包投递率。

    本文协议的一个重要衡量指标是能量分析。在初始阶段，所有节点的能量设置为0.25 J，将0.1 J设置为能量阈值。将本文协议与文献[5]、文献[7]和文献[8]提出的协议进行比较，结果如图7(b)所示。从图7(b)可以看出，本文协议在120 s后网络节点平均能量仍然能够保持70%，很好地均衡了网络节点能量，提高了网络寿命。

3 结束语

    本文提出了一种利用能效优化的自组织位置感知协议，根据主干锚节点的位置感知将网络构建成树结构，利用拓扑控制优化网络的拓扑结构来维持网络的连通性和覆盖范围。同时在路径选择过程中加入节能机制，从而均衡网络负载。在运行过程中，利用自组织方式最小化消息传输和接收次数，降低消息复杂度，减少协议开销。未来研究将会考虑传感器网络快速运动情况。

参考文献

[1] ZENG Y，CAO J，HONG J，et al.Secure localization and location verification in wireless sensor networks: a survey[J].The Journal of Supercomputing，2013，64(3)：685-701.

[2] YU G，YU F.A localization algorithm for mobile wireless sensor networks[C].Integration Technology，2007.ICIT′07.IEEE International Conference on.IEEE，2007：623-627.

[3] CUZZOCREA A，PAPADIMITRIOU A，KATSAROS D，et al.Edge betweenness centrality：A novel algorithm for QoS-based topology control over wireless sensor networks[J].Journal of Network and Computer Applications，2012，35(4)：1210-1217.

[4] 赵雁航，钱志鸿，尚小航，等.基于跳距修正粒子群优化的WSN定位算法[J].通信学报，2013，34(9)：105-114.

[5] VECCHIO M，López-Valcarce R，MARCELLONI F.A two-objective evolutionary approach based on topological constraints for node localization in wireless sensor networks[J].Applied Soft Computing，2012，12(7)：1891-1901.

[6] GENTILE C，ALSINDI N，RAULEFS R，et al.Cooperative localization in wireless sensor networks：distributed algorithms[C].Geolocation Techniques.Springer New York，2013：187-211.

[7] 康一梅，李志军，胡江，等.一种低能耗层次型无线传感器网络拓扑控制算法[J].自动化学报，2010，36(4)：543-549.

[8] LUO X，YU H，WANG X.Energy-aware self-organisation algorithms with heterogeneous connectivity in wireless sensor networks[J].International Journal of Systems Science，2013，44(10)：1857-1866.