基于k元n立方体拓扑的无线传感器网络广播策略

李金宝，倪林雨,郭亚红,任倩倩

(1.黑龙江大学 a.计算机科学技术学院;b.信息科学技术学院，哈尔滨 150080；2．黑龙江省数据库与并行计算重点实验室，哈尔滨 150080)

基于k元n立方体拓扑的无线传感器网络广播策略

李金宝1a,2，倪林雨1a,2,郭亚红1b,任倩倩1a,2

(1.黑龙江大学 a.计算机科学技术学院;b.信息科学技术学院，哈尔滨 150080；2．黑龙江省数据库与并行计算重点实验室，哈尔滨 150080)

研究了无线传感器网络的广播策略，提出一个冲突避免立方体广播算法CACB(Collision Avoidance Cube Broadcast)。CACB基于对k元n立方体结构的网络研究广播策略。CACB算法采用时钟准同步的方法，按照为序寻径的方式，确定每一个时间步应该如何去路由信息。实验使用OPNET软件进行仿真，仿真结果表明基于k元n立方体的无线传感器网络的广播算法CACB和传统的广播策略相比，能够减少最大端到端的时延，降低网络冲突，减少节点能量消耗，延长整个网络寿命,提高了网络的吞吐量。

无线传感器网络；广播；k元n立方体；吞吐量；端到端时延

0 引 言

无线传感器网络目前已经在国防军事、智能家居、城市小区安全监控、环境监测和预报、医疗状况监控、深海监控、目标跟踪和检测、森林火灾监控等众多领域得到了广泛应用[1]。

广播在无线传感器网络中是一种最基本的服务。泛洪法(FLOOD)是所有广播中最简单的方法[2]。这种方法实现简单，当节点收到数据信息就转发给它的邻居节点，并且可传输到网络中的全部节点，但是泛洪法会导致广播风暴[3]。当节点电量用尽时，导致网络不连通，影响了正常通信，因此节点能量的消耗情况决定整个网络的寿命。现有的广播算法已经有了一定的成果，研究出一种更加高效的广播算法仍然具有研究的意义[4]。

泛洪法是所有节点在收到某一广播时间信息后，都将再次转发该数据信息，这种算法的缺点明显，数据将冗余转发，增加了节点的能量消耗和冲突碰撞的可能性。PB算法和泛洪广播算法十分相似，它是基于概率的广播算法，与泛洪法唯一不同的是节点在收到数据消息后以概率进行转发的数据信息。这种算法同样较简单，可以在一定程度上减少冗余转发数据。

1 相关知识与网络模型

1.1 相关知识

无线传感器网络的特点是无线传感器节点能量有限，无线传感器网络使用多跳的传输方式传递信息，无线传感器网络传输能力有限。k元n立方体和超立方体由很多相似之处，具有对称性、低传输时延、直径短等性质，相比二元超立方体在维数相同的情况下能够容纳更多的节点，更适用于部署大量无线传感器节点的情况[5]。k元n立方体的无线传感器网络的广播按照维序寻径，降低无线网络传播冲突，减少数据传输的冗余，由于直径短，传输数据需要的跳数少，减少最大端到端的时延，减少节点能量消耗，延长整个网络寿命[6]。

参数k是沿着每个方向的节点数，n是立方体的维数[7]。这两个数与网络中节点个数N的关系为：N=kn。k元n立方体的每个节点可以用一个n位的序列来唯一标识[2]。一个节点A的地址可以表示为v0v1v2…vn-1，其中vi代表第i维节点的位置，并且0 ≤vi≤k-1。2元3立方体见图1。

图1 2元3立方体Fig.1 2-ary 3-cube

定义汉明距离H(U，V)，对于二进制编码即节点编号相差的位数。例如V1=000，V2=001，H(V1，V2)=1，V1、V2这个两个顶点编号只差一位，即汉明距离为1,V3=111，H(V1，V3)=3，V1，V3这个两个顶点编号相差三位，即汉明距离为3。

定义Vi的邻居集合NBi，即汉明距离H(U，V)=1的顶点集合。例如V1=000的邻居是U1=001，U2=010，U3=100，NB1={U1，U2，U3}；V2=001的邻居是U4=000，U5=002，U6=011，U7=101，NB2={U4，U5，U6，U7}。

1.2 网络模型

图G(V，E，C)，其中V={V1，V2，V3，…，Vn}是图中的顶点集合，图G中每个顶点代表无线传感器网络中的传感器节点。C={C1，C2，C3，…，Cn}是可用的信道集合。E={e(i，j，k)|Vi∈V，Vj∈V，Ck∈C}是图中的边集，如果Vi、Vj在无线发射机的传输范围内，并且节点Vi、Vj使用相同的信道Ck,则Vi、Vj之间有边相连。

冲突定义，两个节点同时向同一节点发送数据时，数据传输时就会冲突碰撞。目的节点接收不到正确的数据信息,见图2。

图2 节点冲突Fig.2 Conflict

定义CS(Collision Set)为冲突集合，当两个节点同时发给另一个节点时，数据信息在传输过程中遇到了冲突，目的节点不会收到正确的信息。例如001发送数据给011，001加入CS集合。010要发送数据给011，首先查询CS集合找到011节点，说明010这时发送给011时会遇到冲突碰撞，010需要等待下一个时间步再发送数据。假设拓扑结构中的每个节点已知自身的地址编码。

2 基于k元n立方体的广播算法

2.1 广播算法

本文中的k元n立方体使用了多Radio多Channel，在立方体的顶点上使用单独的具有远距离通信的信道C2，使其在立方体的顶点上一跳通信，其他除去立方体的顶点具有通信距离较近的信道C1，通过多跳的传输方式，节约能量，立方体的顶点上配有两个Radio实现C1、C2信道。其他除去立方体的最外层顶点只使用单Radio,单Channel，并且Radio使用C1信道。

算法使用的参数定义见表1。

表1 算法参数定义

计算邻居算法见表2，该算法用于计算邻居节点的集合。通过计算得到邻居节点集合可为CACB算法使用。有了邻居节点集合就可以计算CS冲突集合。CS用来限制每一步数据信息怎样传输，使得传输数据时不会遇到冲突，重传数据。

表2 算法1 邻居算法NA

算法2 CACB冲突避免立方体广播算法集中计算全网络的节点应该在每个时间步进行如何接收数据、转发数据，而不需要数据传输或者数据信息接收时，传感器节点可以进入休眠状态来节约节点的能量，在需要数据传输或者数据信息接收时，提前唤醒即可。算法采用时钟同步，每个节点使用CACB算法得到的VTS，得到自身在哪个时间步接收数据、哪个时间步发送数据不会冲突。在确定的时间步，接收发送数据,算法2见表3。

表3 算法2 冲突避免算法

2.2 基于k元n立方体广播算法CACB实例

例如图3中2元3立方体的广播过程。线上的数字代表第多少时间步转发了数据信息。图4用树形图描绘出节点发送信息的过程，树的高度即为广播过程需要的时间步数。

图3 2元3立方体节点在每个时间步发送过程Fig.3 Broadcast process of 2-ary 3-cube

图4 2元3立方体树形图描绘广播过程Fig.4 Broadcast tree of 2-ary 3-cube.

3 仿真实验与性能评估

仿真实验使用OPNET软件进行模拟[8]。泛洪的节点是在200 m×200 m的区域内。本文使用的k元3立方体，其中k=2、3、4、5、6、7分别对应8、27、64、125、216、343个节点进行仿真实验[9]。

首先对比CACB与传统的FLOOD算法、PB算法的最大端到端时延，即传输跳数的比较。其中PB算法采用P=0.8的概率转发数据信息，见图5。CACB与传统的算法相比，在相同节点数量的情况下，最大传输跳数明显减少，即最大端到端时延明显降低。因为采用CACB算法使用的是k元n立方体网络拓扑结构，k元n立方体网络有其自身的优势，按照本文提出的算法，广播时不存在冲突碰撞的可能，并且由于网络的直径短，即传输的跳数减少了。

图5 端到端时延Fig.5 End-to-end delay

其次对比CACB与传统的FLOOD算法、PB算法的能量消耗。其中PB算法采用P=0.8的概率转发数据信息，见图6。CACB与传统的算法相比，在相同节点数量的情况下，节点发送总次数明显减少，即节点能量消耗明显降低。因为CACB算法，按时间步发送数据，形成广播树，每个节点只发送一次数据，所有节点的总发送次数要明显比FLOOD和PB算法要少。

图6 节点能量消耗Fig.6 Energy consumption

最后对比CACB与传统的FLOOD算法、PB算法的吞吐量。其中PB算法采用P=0.8的概率转发数据信息,见图7。CACB与传统的算法相比，在相同节点数量的情况下，广播一次的时间步数少，即节点每个时间步的传输数据分组多。

图7 吞吐量Fig.7 Throughput

4 结 语

本文提出的算法CACB是在k元n立方体的网络拓扑结构来进行广播。CACB算法采用时钟准同步的方法，确定每一个时间步中每个节点应该如何去路由信息，避免了传输数据时遇到的冲突碰撞，最终路由到网络中所有节点，完成广播。实验使用OPNET软件进行仿真，仿真结果表明基于k元n立方体的无线传感器网络的广播算法CACB和传统的广播策略相比，能够减少最大端到端的时延，降低网络冲突，减少节点能量消耗，延长整个网络寿命，提高了网络的吞吐量。

[1]李建中, 李金宝, 石胜飞. 传感器网络及其数据管理的概念、问题与进展 [J]. 软件学报, 2003，14(10):1 717-1 727.

[2]Kai H. 高等计算机系统结构 并行性 可扩展性 可编程性[M]. 北京:清华大学出版社,1995: 67-70.

[3]Ni S, Tseng Y, Sheu J.The broadcast storm problem in a mobile ad hoc network[J].2002,8:153-167.

[4]Wei Y, John H, Deborah E.An energy-effcient MAC protocol for wireless sensor networks[C].Proc. INFOCOM, 2002:1 567-1 576.

[5] Chang C T,Chang C Y,Sheu J P.Bluecube: constructing a hypercube parallel computing and communication environment over bluetooth radio system[C].Proc. International Conference on Parallel Processing (ICPP), 2003:447-454.

[6]Manoharan R, Thambidurai P.Hypercube based team multicast routing protocol for mobile ad hoc networks[C].Proc. International Conference on Information Technology (ICIT). 2006.

[7]Wu J,Wang Y S.Social feature-based multi-path routing in delay tolerant networks[C].Proc. INFOCOM, 2012:1 368-1 376.

[8]Habib S, Marimuthu P.Optimized capacity planning and performance measurement through OPNET Modele[C].Proc. Computer Applications and Industrial Electronics (ICCAIE), 2010:43-48.

[9]Emad A.Network Simulation Experiments Manual[M].Beijing:China Mechine Press,2011:1-20.

A broadcast strategy based on K-ary N-cube topology in wireless sensor networks

LI Jin-Bao1a,2, NI Lin-Yu1a,2,GUO Ya-Hong1b,REN Qian-Qian1a,2

(1.Heilongjiang University, a.School of Computer Science and Technology;b.School of Information Management, Harbin 150080, China; 2.Key Laboratory of Database and Parallel Computing of Heilongjiang Province, Harbin 150080, China)

The wireless sensor network broadcast strategy is mainly researched, it proposes a collision avoidance cube broadcast algorithm CACB. The CACB algorithm uses quasi-synchronous clock and the dimension order routing to determine each time step which should be to routing information and each time step select the determine nodes forward data. The experiment uses the OPNET simulation software, simulation results show broadcast strategy for wireless sensor networks based onk-aryn-cube compared to traditional broadcast strategy that can reduce the maximum end-to-end delay, reduce network conflicts, reduce node energy consumption, prolong the life of the entire network and improve the throughput.

wireless sensor networks; broadcast;k-aryn-cube; throughput; end-to-end delay

10.13524/j.2095-008x.2014.01.014

2014-01-19

国家自然科学基金项目(61370222，61300225)；黑龙江省自然科学基金项目(F201324);黑龙江省教育厅科学技术研究项目(12521404)；黑龙江省高校科技创新团队建设计划项目(2013TD12)

李金宝(1969-)，男，黑龙江庆安人，教授，博士，研究方向:无线传感器网络、数据库、并行计算等。

TP393

A

2095-008X(2014)01-0064-05