基于节点聚类的可伸缩多应用无线传感器网络模拟.doc

第11期李文军等：基于节点聚类的可伸缩多应用无线传感器网络模拟219基于节点聚类的可伸缩多应用无线传感器网络模拟李文军，林宏生，周晓聪，郑尧展（中山大学 信息科学与技术学院，广东 广州 510275）摘 要：提出一种基于节点聚类的无线传感器网络模拟方法，部署同类应用的节点在模拟器中采用单一实体建模，通过多个实体之间的通信实现不同节点的交互，并利用实体之间的同步驱动模拟事件的顺序进行。基于节点聚类方法，在主流模拟工具TOSSIM的基础上设计并实现了一个无线传感器网络模拟器ETMA；实验结果表明，基于节点聚类的模拟方法不仅可支持多应用无线传感器网络的模拟，同时还具有良好的可伸缩性。关键词：无线传感器网络；节点聚类；可伸缩性；多应用模拟中图分类号：TP393 文献标识码：B 文章编号：1000-436X(2008)11-0213-07Scalable and multi-application wireless sensor networks simulation based on node clusteringLI Wen-jun, LIN Hong-sheng, ZHOU Xiao-cong, ZHENG Yao-zhan(School of Information Science and Technology, Sun Yat-sen University, Guangzhou 510275, China)Abstract: A node clustering based approach was proposed to solve effectively the large scale WSN simulation with multiple applications by partitioning nodes into different clusters. Nodes in a single cluster running the same application were simulated with the same single entity. Interactions between nodes were simulated by entity communication, and a synchronous mechanism was also proposed to ensure the simulation events execute orderly. A node clustering based simulator ETMA was designed and implemented on top of TOSSIM. Empirical studies on ETMA show that the node clustering approach can support multi-application WSN simulation with high scalability.Key words: wireless sensor networks; node clustering; scalability; multi-application1 引言无线传感器网络(WSN, wireless sensor networks)1, 2具有网络规模大、节点密度高等特点，这些特点使得无线传感器网络应用程序测试更具挑战性。现有研究提出了许多无线传感器网络应用程序测试的方法、工具和平台，其中使用模拟器进行测试的方法因其具有成本低、模拟环境易控制、效率高以及重编程与重部署方便等特点而在开发无线传感器网络应用中广泛使用。收稿日期：2008-06-10；修回日期：2008-10-10无线传感器网络是一个大规模的网络，网络中不同的节点可能运行不同的应用程序，通过各应用程序之间的协作来完成特定的任务。例如，在一个用于大规模伤亡救援响应的CodeBlue3系统中，需要有多种节点，分别用于监测伤员身体参数、救护人员位置监测及通知求援、基站调度与伤员信息维护等。在对此类无线传感器网络应用的模拟测试中，需要模拟器能够提供大规模的、支持多个应用的模拟。在现有无线传感器网络模拟器中，支持多应用模拟的一种途径是采用每节点单一实体（entity-per-node）模型，亦即将每一个节点建模为一个实体进行模拟，例如ATEMU4、EmTOS5、SNAP6、Viptos7等模拟器均采用此方法。一个实体是指在模拟器中对一个应用的模拟，执行相应节点上的应用程序代码，维护相应节点的数据或状态。这种方法可将部署了不同应用的节点作为不同的实体来模拟，但其缺陷是大大降低了模拟器的可伸缩性（scalability）。对每一节点使用一个实体进行模拟，一方面需要为每一节点运行的数据结构与应用程序分配相应的空间，这在节点数目巨大时会大大降低性能，另一方面在维护所有节点的同步与运行时也需要大量的计算，因而这种模型带来了性能低下以及可伸缩性不高的缺陷，难以实现模拟大规模的无线传感器网络。而像TOSSIM8, 9等模拟器则采用所有节点单一实体（single-entity）模型，亦即将所有节点的模拟都交由同一实体去运行的方法，这使得整个模拟器仅需维护一个应用程序的运行。虽然每一节点拥有单独的数据空间，但所有节点均使用同一应用程序，从而减少了额外的应用程序运行所需的空间，也减少了实体间的协调同步，有效地提高了模拟器的可伸缩性。然而，这种方法却无法支持多应用无线传感器网络的模拟。针对上述问题，文中提出一种节点聚类（node clustering）方法支持无线传感器网络的多应用模拟与可伸缩性。节点聚类又称每应用单一实体（entity-per-application）模型，它将运行同一应用程序的节点集聚到同一个实体中进行模拟，不同的实体运行不同的应用程序，每一份应用程序仅存在于一个实体中，从而减少了采用每节点单一实体模型所带来的相同应用程序的重复空间分配与协调管理，不同节点间的交互只需通过实体间的通信来完成。这样基于节点聚类的方法在支持多应用模拟的同时还具有良好的可伸缩性。文中详细介绍了一种节点聚类的无线传感器网络模拟方法，并在TOSSIM 2.x10的基础上设计并实现了一个可伸缩的、支持多应用的模拟器（ETMA，extended tossim for multiple applications）。借助于TOSSIM在模拟传感器网络时的良好可伸缩性以及可模拟多个节点运行相同应用程序等特点，ETMA在模拟时引入多个TOSSIM副本，每个TOSSIM副本可分别运行一类应用程序，并各自管理一系列运行该代码的节点，节点间的通信通过TOSSIM副本间的协作来实现，ETMA控制模块对多个TOSSIM副本进行控制，实现对多个TOSSIM副本模拟行为的同步以及其中节点的交互进行控制，从而完成对多个应用程序的模拟。针对ETMA的实验表明，节点聚类的模拟方法不仅可支持多应用无线传感器网络的模拟，同时还具有良好的可伸缩性。2 节点聚类在无线传感器网络模拟中，一个应用程序的模拟运行称为一个实体（entity）。一个实体仅执行一个应用程序的模拟，但可包含多份该应用程序所需的数据。模拟器中的一个实体如同操作系统中的一个进程，拥有自身执行的代码，也带有相应的数据结构。节点聚类的方法是指将无线传感器网络中的节点根据应用程序进行分类，将运行相同应用程序的节点归为一类，并使用一个实体来模拟每一类应用程序中的节点，通过多个实体间的通信来实现不同应用节点之间的交互，同步所有实体的模拟运行来驱动整个无线传感器网络的模拟正常有序的进行。如图1所示，节点聚类将左边的真实网络映射为右边的模拟网络进行模拟。在真实网络中，存在多类应用程序，在图1中用不同的图形表示，这些应用程序分别部署在相应的节点上，各个节点之间相互连接构成网络拓扑。节点聚类方法针对不同的应用程序使用不同的实体进行模拟，如图1模拟网络中，每一实体运行一种应用程序，并模拟所有运行这一类应用程序的真实节点的运行。部署了相同应用程序的节点之间的通信在一个实体的内部实现，而部署了不同应用程序的节点之间的交互（如图1模拟网络中虚线所示）则通过多个实体之间的通信来实现。多个实体的运行需要有一个模拟控制器来协调，从而控制实体上运行的应用程序及相应的节点，以及同步所有实体的模拟行为。图1 节点聚类模拟方法在节点聚类模拟方法中，必须解决3个技术要点：节点的组织方式、不同节点之间的交互、实体之间的同步。1) 节点的组织方式。在节点聚类模拟方法中，节点根据不同的应用程序进行分类，部署了相同应用程序的节点聚集在一个实体中运行，从而支持多应用模拟并提高可伸缩性。在典型的无线传感器网络中，大量节点运行同一类应用程序，例如在CodeBlue系统中存在大量节点，但仅由少数几类不同的应用程序组成。由于网络中应用程序种类的数目远远小于节点的数目，因此基于节点聚类的模拟方法相比于每节点单一实体模型具有更高的效率，相对于所有节点单一实体模型而言又具有近似的可伸缩性。2) 不同节点之间的交互。不同节点的交互是多应用模拟需解决的一个主要问题。节点聚类模拟方法将节点的交互分为2个层次：相同应用的节点之间的交互由实体内的网络通信模型来实现；不同应用的节点之间的交互则需通过实体间的通信来实现。实体获取节点向其他实体中的节点发送的消息，将相应的数据及参数传递到目标实体，目标实体接收到消息后，解析消息并调用全局的网络通信模型，将相应的数据传递到目标节点。因而节点聚类模拟方法需要使用一个全局的网络通信模型，以保证所有实体内的网络通信与实体间的通信都是一致的。3) 实体之间的同步。实体不能单独地进行模拟，在整个网络模拟中需要对所有实体的运行进行同步。实体之间的同步保证了整个网络的模拟中，在任一时刻所有实体都具有相同的虚拟时间值。在节点聚类方法中，使用一个模拟控制器的外部模块来控制所有实体的模拟。在离散事件的执行模型中，模拟控制器通过不断地获取所有实体间的事件执行时间，获取所有离散事件中下一个事件的虚拟时间值，驱动所有的实体执行该虚拟时间的事件。可伸缩性是WSN模拟与传统网络模拟的一个不同之处。WSN模拟的可伸缩性不仅取决于模拟的执行模型，还与网络通信模型、环境模型以及电源模型等都有关系11。节点聚类方法主要针对模拟的执行，对于通信、环境及能源模型不作考虑。在节点聚类中，使用一个实体运行相同节点的方式提高了模拟的效率，由于在无线传感器网络中不同应用的数量小，因此实体间的协作少，并不会大量增加模拟中的额外计算，从而使得其可伸缩性相对于实体模拟单一节点的方法要高得多。因此，在无线传感器网络模拟中，节点聚类方法是实现可伸缩、多应用模拟的一个有效解决方案。第3节将详细介绍根据节点聚类的方法实现的一个模拟器ETMA，通过对TOSSIM 2.x的扩展来实现一个可伸缩的、支持多应用的无线传感器网络模拟器。3 ETMA的设计与实现基于节点聚类模拟方法设计并实现的可伸缩的、支持多应用的模拟器ETMA是对TOSSIM 2.x的扩展，提供了同时对多个nesC12应用程序模拟的支持。ETMA保持了TOSSIM在模拟上所具有的可伸缩性，同时增加了模拟异构网络的功能。如图2所示，ETMA把运行于同一种程序的节点看为一组，将其在一个扩展TOSSIM实例（ETI，extended TOSSIM instance）上进行模拟，由ETI运行不同的nesC代码，而由控制模块（CM，control module）来协调所有ETI之间的模拟运行，由此来模拟整个传感器网络。图2 ETMA体系结构每个ETI都是一个模拟nesC应用的实体。ETI含有原来TOSSIM上完整的组件，包括顶层应用程序组件、TinyOS组件与TOSSIM底层的硬件抽象组件。每个ETI之间能通过CM的协调进行通信与交互。所有的ETI共享一份模拟环境，包括各节点之间的连通度。ETI之间不直接连接，而由CM中转。控制模块相当于是ETMA的模拟控制器，其功能是将分离的ETI连接起来，让ETI之间能够进行交互，统一对所有的ETI进行协调与同步。CM是ETMA的控制中心，负责实现消息转发、时间同步的功能。如图3所示，TOSSIM按原有方式负责应用程序的模拟。在ETI中，对TOSSIM节点数据包发送的处理进行了重定向，通过调用ETMA核心模拟（DMT，data delivery, mote management, and Time synchronization）提供的接口对数据包进行转发，其他功能则保持与原TOSSIM一致，使ETI在模拟中保持有原TOSSIM在模拟上所具有的优点。TOSSIM不直接与控制模块相连接，而是通过DMT作为中介与其交互。图3 ETMA核心模块及其交互DMT为多种程序共同模拟提供所需的同步控制与数据转发功能。DMT一方面与TOSSIM连接,使用TOSSIM无线通信模型与执行模拟提供的接口对程序的模拟进行控制，另一方面与控制模块连接，使用CM的接口进行消息转发，并提供相应的功能接口为CM所调用。ETI与DMT紧密相关，每个ETI都由一个DMT来维护与其他ETI之间的协调与通信，并由DMT控制TOSSIM的执行。CM是ETMA的中心控制器与路由器，对整个系统的运行起着控制的作用。CM维护所有的ETI信息，并调用ETI提供的接口，对整个系统进行协调。此外，CM还充当路由器的角色，将ETI需要转发的消息包转发至相应的ETI，并提供接口为ETI所调用。在模拟器中实现节点聚类方法的关键是DMT模块。DMT模块中的节点管理提供节点的组织方式；DMT中的数据传输与控制功能提供的数据转发机制解决不同节点之间的通信；而DMT中的时间同步与控制功能中的模拟执行机制则实现了不同实体之间的同步。DMT主要功能如下：1) 节点管理。各个ETI需要对所模拟的节点进行管理。节点管理用于每个ETI对本身节点的启动与模拟运行，以及在节点通信时对数据包的源与目标进行判断来实现数据传输。每个ETI维护自己所模拟的节点信息，而控制模块需要维护一个全局的节点与ETI的映射表。控制模块的映射表用于数据转发时对消息的目标地址进行解析并路由。在ETMA中，各个ETI维护一个节点列表来管理其所模拟节点信息，而所有ETI的节点表通过控制模块在模拟初始化时统一设置，控制模块通过使用节点与ETI之间的映射表进行全局的节点管理，使得整个网络上的节点能正确地分布到各个实体中进行模拟。2) 数据传输。ETMA中的数据传输是指不同节点间的通信。对于同一ETI中的节点通信，ETMA使用TOSSIM内部的通信机制实现。而对于不同节点的通信，ETMA通过修改TOSSIM的无线通信机制，添加对消息目标地址的检测，对于非本ETI中节点的消息通过直接传递到控制模拟，由控制模块进行路由来实现。DMT模块的数据传输功能包括2方面：一是负责将消息传递到控制模块；一是接收由控制模块转发过来的数据，并生成相应节点的消息接收事件，将该事件添加入模拟的离散事件队列中等待执行。控制模块的消息转发机制通过解析消息的目标地址，并查找节点与ETI的映射表，获取消息的目标ETI，然后将该消息转发到相应的ETI上，由DMT模块进行处理。ETMA利用TOSSIM原有的无线通信模拟，添加了不同节点间的通信机制，来实现多应用的模拟。3) 时间同步。TOSSIM使用的是离散事件队列的执行模型，模拟中的虚拟时间与实际时间不同。当多个ETI同时运行时，需要对各个ETI进行同步，来保证各个ETI中的事件能顺序进行，也保证整个ETMA中在任何时候所有ETI都处于相同的虚拟时刻。在ETMA中，DMT模块的时间同步功能用于调用TOSSIM执行模型中的接口驱动下一事件的运行，以及返回控制模块下一事件的执行时间。ETMA的时间同步主要由控制模块中的模拟执行来实现，该模块通过顺序地执行所有ETI中的事件来实现同步。控制模块每次需要对所有的ETI进行询问，获得各个ETI下一事件执行的虚拟时间，取得距离当前时间最近的事件，设置系统的时间为该事件的执行虚拟时刻，并驱动相应的ETI执行相应事件。控制模块通过不断地执行各ETI中的事件来驱动整个网络的模拟。ETMA通过对TOSSIM进行扩展，实现多应用模拟。第4节通过对ETMA的实验与评价讨论ETMA对多应用模拟的支持以及具有与TOSSIM相似的可伸缩性。4 实验与评价本小节使用CntToRfm与RfmToLeds 2个经典的nesC应用测试与评价ETMA对多应用程序模拟的支持及其可伸缩性。CntToRfm应用程序在节点上维护一个计数器，每250ms计数增加一次后就将计数值广播出去，而RfmToLeds应用程序则是节点接收到消息后，将消息中的计数值提取出来，并通过LED进行显示。本文使用2个节点运行这2个程序。节点1运行CntToRfm，节点2运行RfmToLeds，节点1与节点2相互连通。使用ETMA模拟的屏幕画面如图4所示。图4 ETMA多应用模拟在图4所示的模拟中，节点1与节点2进行通信传递计数器的值，节点1的发送与节点2的接收顺序进行，ETMA实现不同节点的通信，保证了模拟的顺序进行，实验表明ETMA能够实现包含多个应用程序的无线传感器网络模拟。可伸缩性是ETMA相对于其他支持多应用的模拟器而言的一个特点。TOSSIM具有优秀的可伸缩性，支持模拟具有上千节点的无线传感器网络，而ATEMU与EmTOS的可伸缩性都不高。这里主要通过与TOSSIM的可伸缩性相比，来说明ETMA在无线传感器网络模拟上具有与TOSSIM相似的可伸缩性。本文采用2类应用程序测试模拟器的可伸缩性，分别代表了在网络处于静止状态与活动状态情况下ETMA与TOSSIM的性能比较。第一个应用程序是CntToLeds，该程序中节点每250ms生成一个计数器值，并将该计数器通过LED显示出来。该应用程序不使用无线网络进行通信，代表网络处于静止状态，可表示模拟器所能到达的最高性能。第二个应用程序是RadioCountToLeds，它也是以4Hz的频率发送计数器的值，再接收计数器的值并显示，节点每次将消息发给所有相邻的节点，频繁地发送与接收消息，代表网络处于繁忙的情况。使用该程序可比较ETMA与TOSSIM在使用网络时的可伸缩性。在实验中使用全连通网络测试最繁忙的网络通信情况。TOSSIM上运行同一应用，而ETMA上则分别运行2个逻辑上相似的应用，它们只是在计数值的增量上不同。模拟时，每个节点同时启动并分别模拟运行10个虚拟秒的时间，通过模拟所需要的实际时间来比较ETMA与TOSSIM 2.x的可伸缩性。如图5所示，ETMA所需时间与TOSSIM非常相近。可以看出，在无网络通信的情况下，ETMA与TOSSIM具有几乎相同的可伸缩性，在各种节点规模均可很好地达到TOSSIM本身的性能。图5 模拟CntToLeds运行10虚拟秒所需时间图6是RadioCountToLeds程序在2个模拟器上运行的实验结果。可看出，相对于TOSSIM，ETMA的模拟时间稍稍增大，其运行的时间大约比TOSSIM慢了15%20%。这是由于ETMA中需要对多个ETI进行协调，以及处理多ETI之间的通信，导致消耗额外的时间。从图中也可看到，这些操作并不会减弱模拟的可伸缩性。ETMA与TOSSIM两条时间曲线的几乎一样，也就是说，ETMA在节点之间需要进行网络通信的情况下所具有的可伸缩性也是一样的。图6 模拟RadioCountToLeds运行10虚拟秒所需时间从上述2种情况可以看出，ETMA在进行2个应用的模拟时具有与TOSSIM相似的可伸缩性。下面对于通过针对多个应用的情况来评价应用数目与模拟的可伸缩性之间的关系。在实验中同样对上述2个程序进行模拟，对于CntToLeds，仍通过计数器值的不同来模拟不同的应用，并比较这些应用在模拟1 024个节点的网络10虚拟秒的实际时间。对于RadioCountToLeds，实验模拟256个节点运行10虚拟秒的时间。实验结果如图7所示。从图中可看出，模拟所需的实际时间随着应用数目的增加而增加。在这2种情况的模拟中，当应用数目小于16时，模拟时间的增长幅度很小，而当应用数目增长到32或64时，可看到模拟时间出现明显的增长。从上述的模拟结果可以看出：应用数目会影响模拟的可伸缩性，应用数目的增加会延长模拟时间；在应用数目较少的情况下，ETMA能保持与TOSSIM相似的可伸缩性，而在应用数量较大的时候，ETMA的模拟时间会出现大幅度的增长，大大降低可伸缩性。图7 应用数目与可伸缩性的关系在极端情况下，当所有的节点都运行不同的应用时，节点聚类就会退化为每节点单一实体模型，其可伸缩性会明显减弱。然而，现实的无线传感器网络应用，通常都具有节点数量巨大而所运行的应用数目较少的特点，例如在CodeBlue系统中只需较少应用数目的支持。由于无线传感器网络上的应用数目通常远远少于节点的数目，因此相对基于每节点单一实体模型的模拟方法而言，节点聚类模拟方法大大减少了实体的数目，从而具有更高的可伸缩性。由上述分析与实验评价数据可看到，ETMA在无线传感器网络的模拟上具有与TOSSIM近似的可伸缩性，而TOSSIM本身具有良好的可伸缩性，大大优于每节点单一实体方法的模拟器，这也表明ETMA在可伸缩性上远远优于如ATEMU之类的其他多应用模拟器。无线传感器网络应用的特点之一就是节点数目巨大，ETMA的可伸缩性更好地满足了对无线传感器网络应用的测试需求。从无线传感器网络的模拟测试方法看，ETMA的实验与评价也表明，基于节点聚类的模拟测试方法能够在支持多应用模拟的同时具备高可伸缩性，该方法具有与所有节点单一实体模型近似的可伸缩性，远高于每节点单一实体模型的模拟效率。因此，节点聚类方法为无线传感器网络模拟支持多应用与高可伸缩性提供了一个良好的解决方案。5 结束语模拟是无线传感器网络测试的一个重要方法。无线传感器网络包含大量的节点，节点可能运行多个不同类型的应用，这就要求模拟能够支持大量节点与多应用的模拟，现有模拟方法在这方面都存在着一定的不足。本文提出节点聚类的方法，通过将运行同一应用的节点聚为一类在一个实体中进行模拟，并通过多个实体的通信实现不同节点的交互，以及实体的模拟同步来驱动模拟的顺序进行。节点聚类在支持多应用模拟的同时，也具有高的可伸缩性。参考文献：1孙利民, 李建中, 陈渝. 无线传感器网络M. 北京: 清华大学出版社, 2005.SUN L M, LI J Z, CHEN Y. Wireless Sensor NetworkM. Beijing: Tsinghua University Press, 2005.2AKYILDIZ I F, SU W, SANKARASUBRAM-ANIAM Y, et al. Wireless sensor networks: a surveyJ. Computer Networks, 2002, 38(4): 393-422.3LORINCZ K, MALAN D J, FULFORD-JON-ES T R F, et al. Sensor networks for emergency response: challenges and opportunitiesJ. IEEE Pervasive Computing, Special Issue on Pervasive Computing for First Response, 2004. 3(4): 16-23.4POLLEY J, BLAZAKIS D, MCGEE J, et al. AT-EMU: a fine-grained sensor network simulatorA. Proceedings of the First IEEE Communications Society Conference on Sensor and Ad Hoc Communications and NetworksC. 2004. 145-152.5GIROD L, STATHOPOULOS T, RAMANATHAN N, et al. A system for simulation, emulation, and deployment of heterogeneous sensor networksA. Proceedings of the Second International Conference on Embedded Networked Sensor SystemsC. 2004. 201-213.6KELLY C IV, EKANAVAKE V, MANOHAR R. SNAP: a sensor network asynchronous processorA. Proceedings of the Ninth International Symposium on Asynchronous Circuits and SystemsC. 2003. 24-33.7CHEONG E, LEE E A, ZHAO Y. Viptos: a graphical development and simulat