无线传感器网络中基于聚簇的域连接算法

王建明¹，刘建成²

 (湖南商学院 计算机与电子工程系，湖南 长沙，410205；

2. 中南大学 信息科学与工程学院，湖南 长沙，410083)

摘  要：针对无线传感器网络中数据处理时节能效率不高的特点，提出一种有效节能的域连接算法(Regions join algorithm, RJA)。该算法首先结合传感器网络的节点特性和位置信息，提出一种基于聚簇的定向传播模型，该模型把传感器网络按域的划分来构建聚簇，查询只需在聚簇中进行，因而能有效减少传感器网络中信息传输的时间复杂度，同时利用网络中虚电路连接的思想，只将连接属性中与匹配相关的数据投送到链路中的公共区域进行比较运算，并不需要把整个信息表在网络中传送，因而能提高链路传输的效率。理论分析和实验结果表明，该算法与传统算法相比节省能量。

关键词：无线传感器网络；聚簇；定向传播模型；区域连接

中图分类号：TP393         文献标识码：A         文章编号：1672-7207(2009)01-0195-05

Regions join algorithm based on domain clustering in

 wireless sensor networks

WANG Jian-ming¹, LIU Jian-cheng²

 (Department of Computer and Electronic Engineering, Hunan Business College, Changsha 410205, China;

2. School of Information Science and Engineering, Central South University, Changsha 410083, China)

Abstract: Based on the power-effective deficiency in query processing for wireless sensor networks, a novel two regions join algorithm called RJA (Region join algorithm) was proposed. In RJA, considering the characteristics and location information of nodes in sensor networks, a modified directed transfer model of sensor networks and a novel clustering algorithm based on domain were proposed. The clustering core was constructed by the core node and gateway node, and the query could transmit in the domain clustering. Enlightened by the virtual circuits in the internet, the novel semi-join technique was used in the RJA, where only the data of join attribution in stead of the data of whole information table was sent to the region, therefore, the efficiency of data transfers was better improved than the traditional way. Theoretical analyses and simulation results show that the new methods can efficiently reduce the energy costs of nodes in data transferring in wireless sensor networks, compared to the traditional algorithms.

Key words: wireless sensor networks; distributed; select disposal; domain join

无线传感器在环境与军事监控、地震与气候预测、地下、深水以及外层空间探索等许多方面都具有广阔应用前景^[1-5]。在传感器网络中，连接查询被广泛地应用于目标探测或目标跟踪。要查询同一物体在不同区域的活动时需要用到连接查询^[5-6]。连接查询是指其他节点或者节点的其他属性满足指定条件时，获得节点的感知属性值，最基本的连接操作是等值连接。连接操作是传感器网络中最耗能的操作之一，连接顺序不同，连接的代价可能会有很大的差别^[7]。在传感器网络环境中，传感节点随时都有可能失效，其网络层只能提供非常有限的服务质量保证，每个传感节点只有非常有限的存储容量、计算能力和电池能量。因此，查询处理中必须相互配合，进行有效的资源管理，尤其是能源管理，来提高网络的生命周期^[8-9]。基于此，谢志军等^[9]提出了传感器数据流的连接算法PTRJ，该算法可以提高整个网络的能量利用效率，但并不适合于大规模传感器的场景。Vishal等^[10]提出了一种能源有效的两区域连接查询算法，在此基础上，Aditi等^[9]提出了一种基于Hash的分布式索引连接算法(Distributed hash-based algorithm)，该方法使用hash函数和一种索引来进行Join运算，它的分布性性能更好，但节能效率不高^[12]。在此，本文作者提出一种能量有效的区域连接算法RJA(Region join algorithm)。该算法利用计算机网络中虚电路连接的思想，只是把连接属性中的组元投送到路径中的某个区域进行匹配运算，并不需要把整个连接表在网络中进行发送，理论分析和试验结果表明，本文作者提出的算法与原有算法相比能更好地节省能量。

1  有效节能的区域连接算法RJA

1.1  基于连通支配集的定向传播模型

以前的定向传播模型中,由于在中心节点(Center Node,CN)到传感器节点的兴趣发布过程中建立了用于数据回传的梯度,因此，不需要源节点对CN再次寻径^[13]。这样，可以减低部分寻径开销,但也减低了数据汇聚的性能,增加了数据传输的开销。研究表明:在传感器网络中,数据传输的开销为主要开销^[9]。为此,在网络信息传输中需要降低数据传输的开销,以进一步减低传感器网络的整体能量消耗,延长整个网络的生命周期。本文正是基于此理念来进行节能。

对文献[2]提出的定向传播模型进行改进。首先，将整个传感器网络划分成若个连通的独立区域，每个区域由中心节点(又称簇头)和网关节点组成；簇头节点负责对数据进汇聚。在网络的数据传输过程中，源节点负责在回送监测数据给CN时,其仅在连通区域中进行寻径，即在连通区域的簇头节点间进行寻径。显然,这样可以有效提高源节点的路由效率，降低整个网络的能量消耗。将这种仅在连通区域的簇头节点间寻径模型称之为面向聚簇的定向传播模型。

面向聚簇的定向传播模型中假定在传感器网络中各节点具有相同的有效通信距离，称2个节点是相邻的,即存在一条通信链路,当且仅当这2个节点在彼此有效通信距离之内。假定相邻节点之间的链路是对称的, 则面向聚簇的定向传播模型可以看作是一个带权无向图。表示为G=以及节点的集合U∈V, 其中，W={w(e)|e∈E}表示各边的权值。若任意传感节点e，其对CN节点R的相对坐标为(x, y), CN节点S到各网络节点具有相同或相似的传输路径R，则称e∈域(m, n), 当且仅当如下公式成立:

，。

其中：“|”为除法运算符；“[ ]”为取不小于的整数运算符；N为当时域中节点的个数。

在面向聚簇的定向传播模型中，传感器网络中的域节点e将不采用地址坐标作为网络的标识ID, 而是以节点e提供的数据作为寻址ID。即CN节点在传感器网络中传输是以某种数据格式构成的消息, 询问它所需要的监测节点e中的数据, 并回送监测数据给中心节点CN ^[9]。

由以上对面向聚簇的定向传播模型的定义，可以引出以下2条引理：

引理1  若传感器网络中Center节点S到各网络节点具有相同或相似的传输路径R，则该传感器网络中存在唯一的域划分，且同域中的各网络节点互为邻节点。

引理2  若图G是带权无向图，则由该定向传播模型得到的节点集K={p|p为核心节点且p?V}是图G的一个聚簇，且该聚簇具有唯一性。

由引理2可知：由定向传播模型得到的节点集K构成了一个带簇头的连通支配集。因此，将网络中的节点按区域划分形成带权的连通集来构建聚簇,传感节点只需要在聚簇中进行寻径，这样，可以有效降低数据传输的开销。

1.2  有效节能的区域连接算法RJA

由定向传播模型可知，传感器网络可以按照区域来进行划分，其中核心节点和网关节点能构建成聚簇，查寻命令和查询结果只需要在聚簇中进行转发。本文提出的有效节能的区域连接算法RJA在面向聚簇的定向传播模型上构建并且能实现了连接操作。连接操作的定义可以参考文献[9]中的说明。

假设每个区域都存在1个核心节点和1个网关节点，在核心节点处保留了整个区域的信息连接交换表IT(Information Table)。其中，IT表中保留了本域内传感节点采集到的数据，网关节点主要负责区域间的数据通信问题；同时，假定网络中存在要连接的2个区域为A和B，它们的核心节点处保留了各自的信息表IT_A 和IT_B , 其连接属性为JA(Join attribute)，且域A和域B是由面向聚簇的定向传播模型生成的2个域，它们的核心节点以及网关节点构成了一个聚簇，数据在聚簇中进行传输。从引理1可知，域A和域B传送数据的路径必然会在某一处相交。假设相交的区域为域S。区域S的确定较容易实现。

因为域A和域B在聚簇处保留了信息交换表IT，IT中保留了本域内传感节点采集到的数据。本文作者对文献[9]中的方法进行改进，其思路是：连接信息将在公共区域S处进行比较运算，分为小于、等于和大于这3种情况进行讨论，得到可以参加连接的数据信息后再返回给源节点中，源节点收到的信息将满足连接条件的数据通过寻径最佳线路传输到CN节点进行连接运算，而不用将连接数据信息在整个网络中传输，从而节省了数据传输的开销，同时保证了整个连接过程的有效性和可靠性。域S上的节点将符合连接条件的数据信息分别反馈给源节点，源节点根据相关信息，将符合连接条件的连接属性有趣信息寻找出来，发送到中心节点来进行连接运算。整个连接运算过程如图1所示。

从以上分析可知，域A和B一定会在路径的某处相交，而且在定向传播模型形成以后，传感器网络中的相关区域已经构建了一个聚簇，查询的专发和结果数据的回送都只需要在该聚簇中进行寻径。CN在查询下发时就可以计算出一条本查询需要的2个区域的初始路径，并把这个初始路径记录在查询包中，然后，查询包根据这个路径转发。在查询包的转发过程中再根据包的实际路径对路径进行调整。当查询包到达核心节点后，核心节点根据查询包中的路径信息就可以计算(如比较运算)出2个区域最近的连接地点。

若无线传感器网络中，有新节点x加入该网络中，则该新节点加入定向传播模型时的策略如下：

a. 点x新加入时根据其自身的地理位置计算自己所属于的区域，其初始状态为成员；

b. 节点x把自己的ID号连同请求加入消息发送给核心节点H；

c. 核心节点H 接收到节点x的请求加入消息后，更改本区域内节点信息的表VT，同时向节点x发送允许加入信息；

d. 节点x收到核心节点的允许加入信息后，把产生的数据发送给中心节点进行数据的连接运算。

由图1可以看出，核心节点CN向下发出查询信息，通过域A和B相连的域S发送信息，同时，域A和域B把连接属性发送到路径交汇区域S，S同时将参与连接的元组信息反馈给A和B，A和B将参与连接运算的元组传输至CN进行连接运算。该信息连接的方式类似于互联网的网络层中虚电路的数据传输方式，可以减少传感器网络中信息传输的路径，能有效地节约能量。设为区域S的连接属性，m为该区域中节点的个数，则在区域S中需要/m个节点进行信息存储。

(a) CN向下发出查询；(b) 域A和域B把连接属性发送到路径交汇区域D；(c) D将参与连接的元组信息反馈给A和B；

(d) A和B将参与连接运算的元组路由到Sink进行连接运算

图1  两区域连接算法示意图

Fig.1  Sketch map of two regions join algorithm

有效节能的区域连接算法RJA，具体描述如下：

a. CN节点初始化查询网络中的变量信息，然后，将由定向传播模型构建的聚簇中转发到各核心节点处；

b. 聚簇的核心节点IT_A收到聚集命令后，根据选取的关系开展查询，同时，对IT_A的连接属性Atr( )排序；

c. 根据域A和B的传输链路，计算出两域交汇的域S，并在交汇区域S的核心节点附近连续选取/m个节点备选；

d. 将域A中符合要求的连接属性发送到域S中的核心节点上，然后，将域B按S中节点对应值的范围发送到S中节点上进行比较运算。

① 若做小于运算，IT_A.AtrB.Atr, 则从第1个数据开始匹配，直到在数据中找到一个比IT_B.Atr(k)大的元组结束；

② 若是等值连接，则从IT_B中选取一元组投射到S中，遇到相等的就把元组号记录到结果集中，直到IT_B 中的元组匹配完为止；

③ 若是大于运算，IT_A. Atr>IT_B.Atr(k),则从最后一个开始匹配，直到在数据中找到一个比VS_B.Atr(k)小的元组结束为止；

e. 将符合连接条件的数据信息分别反馈给域A和域B，域A和域B分别将IT_A, IT_B中符合条件的元组整理成关系IT_A′, IT_B′；

f. 域A和域B中的核心节点将找到一条到CN的最短路径，将IT_A′，IT_B′传送到CN节点进行连接运算；

g. 域S中的核心节点等待下游的核心节点传来的数据，进行连接运算。重复此过程，直到所有信息都到达CN为止。

本连接算法中信息的传输空间只在区域A，B和两者相连的区域进行，而不需在全部的空间范围寻  径，明显减少寻径路程，大大降低寻径的时间复杂度。

性质1  连接算法具有相对于域内节点数及域间数线性规模的时间复杂度。

证明  算法执行的代价主要在步骤c~e循环及步骤g循环。对于步骤c~e的循环：需要对区域中的每个节点和距CN节点的区域数，然后，找出最优的路径。这样，每个节点和每个区域都需且只需计算1次，其复杂度为，其中n为域间节点数，e为区域数。步骤g循环主要是给出其最佳路径，易知其时间复杂度为区域的路径长度为。一般来说，远远小于多段图算法类比，故算法总的时间复杂度为。证毕。

2  算法性能分析及试验结果

通过模拟实验对本文模型及相关信任机制进行测试，硬件环境：CPU 为Intel Pentium IV 2.4 GHz，内存为2 048 MB，操作系统为Windows XP。算法实现工具为VC6.0。

对能量有效区域连接算法RJA进行仿真试验，并对实验结果进行分析比较。模拟试验的参数如下： node number：10 000；Link quality：100%；Size of each query region 0.5%(70×70)；Number of tuples per node 100；Number of attributes per tupel6；Join selectivity factor(JSF) 0.000 5；Number of attributes per join tuple 5-10；节点的唯一标识为节点ID，并且每个节点都知道自己的位置，域的组织方式由定向传播模型生成，每个域一个核心节点，核心节点掌握着路由和本域节点的信息，核心节点和网关节点构建成连通核。模拟试验主要是考察PTRJ算法^[9]，Path-join算法^[10]和Distributed Hash-based Join^[11]在改变节点数目时比较节点的平均能量消耗的情况。

考察RJA与Path-join，Distributed Hash-based Join和PTRJ算法在不同节点密度和节点数目下网络的节点平均能耗情况，利用模拟工具生成5组不同的密度和节点数目的网络结构，如图2和图3所示。从图2和图3可以看出，在相同的网络密度和节点数目下，RJA较Path-join，Distributed Hash-based Join和PTRJ算法有较好的性能。这是因为RJA算法采用了半连接的方法过滤掉了区域内的非连接元组，减少了更多的数据传输量，并且不必像Path-join算法那样将A中的所有元组向D中的节点广播，而是将IT_A，IT_B的连接属性数据分发到D中不同节点上，因此，节省了通信能量，同时，也降低了节点的负载和计算量。由于节点的通信能量要远远大于节点的计算能量，与IT_A.Atr( )相比，IT_B.Atr( )计算能量可以忽略。图2和图3所示为4种算法实际能量消耗比较结果，可    见，随着节点数和密度的增加，RJA算法比Path-join，Distributed Hash-based Join和PTRJ算法更加节省能量。

1—RJA算法; 2—Path-join算法;

3—Hash-join算法; 4—PTRJ算法

图2  节点密度对能量消耗的影响

Fig.2  Impact of node density on energy used

1—RJA算法; 2—Path-join算法;

3—Hash-join算法; 4—PTRJ算法

图3  节点数目对能量消耗的影响

Fig.3  Impact of sensors’ number on energy used

3  结  论

a. 结合传感器网络的节点特性和位置信息，提出了一种基于域的分布式数据汇聚模型，该模型把传感器网络按域划分来构建连通核，查询只需在连通核中寻径，能明显减少寻径时间复杂度并且具有更好的分布性。

b. 参考计算机网络中虚电路连接的思想，结合基于域的数据聚集分布式模型，提出了一种有效节能的域连接算法RJA。

c. 该算法只需将连接属性中的信息投送到路径中的某个区域进行比较运算，并不需要把整个连接表在网络中进行发送，因而能较好地提高链路传输的效率。

参考文献：

[1] Akyidiz I, Su W, Sankarasubramaniam Y, et al. A survey on sensor networks[J]. IEEE Communications Magazine, 2002, 40(8), 102-114.

[2] 谢志军, 王 雷, 林亚平, 等. 无线传感器网络基于数据压缩的汇聚算法研究[J]. 软件学报, 2006, 17(4): 860-867.
XIE Zhi-jun, WANG Lei, LIN Ya-ping, et al. An algorithm of data aggregation based on data compression for sensor networks[J]. Journal of Software, 2006, 17(4): 860-867.

[3] Wendi B H, Anantha P C, Hari B. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE transaction on wireless communications, 2002, 1(4): 660-670.

[4] SU Kuo-feng, OU Chia-Ho, JIAN Hua-chun. Localization with mobile anchor points in wireless sensor networks[J]. IEEE Transactions on Vehicular Technology, 2005, 54(3): 1187-1197.

[5] 任丰原, 黄海宁, 林 闯. 无线传感器网络[J]. 软件学报, 2003, 14(7): 1282-1291.

REN Feng-yuan, HUANG Hai-ning, LIN Chuang. Wireless sensor networks[J]. Journal of Software, 2003, 14(7): 1282-1291.

[6] 李建中, 李金宝, 石胜飞. 传感器网络及其数据管理的概念、问题与进展[J]. 软件学报, 2003, 14(10): 1717-1727.
LI Jian-zhong, LI Jin-bao, SHI Sheng-fei. Concepts, issues and advance of sensor networks and data management of sensor networks[J]. Journal of Software, 2003, 14(10): 1717-1727.

[7] Manjeshwar A, Agrawal D P. TEEN: A protocol for enhanced efficiency in wireless sensor networks[C]// Int’l Proc of the 15th Parallel and Distributed Processing Symp. New York: IEEE Computer Society, 2001: 2009-2015.

[8] 孙利民, 李建中, 陈 渝, 等. 无线传感器网络[M]. 北京: 清华大学出版社, 2005.
SUN Li-ming, LI Jian-zhong, CHEN Yu, et al. Wireless sensor networks[M]. Beijing: Tsinghua University Press, 2005.

[9] 谢志军, 陈 红. 传感器网络中能量高效的区域连接算法研究[J]. 计算机研究与发展, 2007, 44(z3): 50-54.
XIE Zhi-jun, CHEN Hong. Researches on energy efficient region join in sensor networks[J]. Journal of Computer Research and Development, 2007, 44(z3): 50-54.

[10] Vishal C, Himanshu G. Communication-efficient implementa- tion of join in sensor networks[C]//Proceedings 10th International Conference on Database Systems for Advanced Applications (DASFAA). New York: IEEE Computer Society, 2005: 447-460.

[11] Aditi P, Himanshu G. Communication-efficient implementation of range-joins in sensor networks[C]// Proceedings 11th International Conference on Database Systems for Advanced Applications(DASFAA). New York: IEEE Computer Society, 2006: 859-869.

[12] 方维维, 钱德沛, 刘 轶. 无线传感器网络传输控制协议[J]. 软件学报, 2008, 19(6): 1439-1451.
FANG Wei-wei, QIAN De-pei, LIU Yi. Transmission control protocols for wireless sensor networks[J]. Journal of Software, 2008, 19(6): 1439-1451.

[13] 林亚平, 王 雷. 传感器网络中的分布式数据汇聚层次路由算法[J]. 电子学报, 2004, 32(11): 1883-1889.
LIN Ya-ping, WANG Lei. A distributed data-centric clustering hierarchical routing algorithm for sensor networks[J]. Acta Electronica Sinica, 2004, 32(11): 1883-1889.

收稿日期：2008-08-25；修回日期：2008-12-02

基金项目：湖南省科技攻关资助项目(05JZ2018)；湖南省自然科学基金资助项目(06JJ5110)

通信作者：王建明(1962-)，男，湖南嘉禾人，副教授，从事传感器网络、智能控制等研究；电话：0731-8689084；E-mail: wjm6686@126.com