蒋林林，刘　峰

（1.重庆邮电大学光通信与网络重点实验室，重庆400065；2.工业和信息化部电信研究院西部分院，重庆401336）

无线传感网络节点内存管理机制的研究与设计

蒋林林1，刘峰2*

（1.重庆邮电大学光通信与网络重点实验室，重庆400065；2.工业和信息化部电信研究院西部分院，重庆401336）

针对现有无线传感器网络WSNs（Wireless Sensor Networks）节点片上RAM（随机存储器）利用率低的特点，设计了一种基于链表的改进型内存管理方案。该方案以事件驱动开发模式为程序运行的前提，在将RAM划分为静态内存空间和动态内存空间之后，通过内存隔离技术，实现内存管理结构与内存空间在实体内存中的分离，从而达到提高节点内存利用率的目的。经测试，写内存的平均速率能够达到500 kbit/s，而在开启内存交换功能时，实际内存的使用率接近80%。最终为提高节点内存利用率提供了一种良好的解决方案。

无线传感器网络；内存管理；内存隔离；事件驱动；内存交换

内存分配策略总体可分为静态内存分配和动态内存分配两大类［1］。系统采用静态内存分配方式时，由于程序在编译和链接时已分配好所需的内存空间，因此采用这种内存分配方式的系统具有实时响应快和内存管理结构简单的特点。但是这种分配方式是按照在最坏情况下进行的内存分配，因此内存利用率通常都很低。采用动态内存分配方式的系统则是将按照用户的实际需求进行内存分配。由于内存的按需分配方式，使得使用该内存分配方式的系统的内存利用率比前者高得多［2］。实际应用中，为兼顾内存分配效率和利用率，无线传感器网络操作系统［3-4］的内存分配方式同时采用了这两类。可是使用这种混合式的内存分配方式的系统，其内存利用率还是没能达到令人满意的程度。

因此，设计本内存管理方案的目的是进一步提高内存的利用率。该方案以无线传感器网络操作系统基于事件驱动［5-10］为前提，使用片上Flash存储内存数据，以此进一步提高了内存的利用率。

1　系统整体架构

基于链表的改进型内存管理机制的整体架构如图1所示。总体上，节点的内存被划分为静态内存和动态内存。对于静态内存，内存管理单元在节点的初始化阶段就以系统预定义的内存分配“粒度［11］”进行内存分配；对于动态内存，存管理单元在收到用户的动态内存分配请求时才进行内存分配。为方便管理内存管理结构，我们将内存管理单元分配的首个内存管理结构的地址保存在与其对应的类型和地址查找表中。系统的内存管理结构被内存管理单元作为管理节点内存的操作对象，因此内存管理单元对节点内存的管理实际上就是对内存管理结构的管理。为了反向标记内存数据对应的内存管理结构，我们在该管理机制中将引入一种被称为“内存地址反向映射［12］”的机制。该机制使得内存管理单元在实现逆向查找内存数据对应的管理结构的的同时还能为实体内存空间的操作提供一定的合法性检测。为简化内存管理，我们借鉴了现代操作系统中使用的“页面［13］”划分技术，实现一种被称为“类页面”的机制。

图1　内存管理整体架构

2　内存管理相关结构设计

2.1类型与地址查找表

该表格被用来保存与其表示类型相对应的管理结构的地址，其定义的结构与内存管理结构的关系如图2所示。

图2　类型与地址查找表与管理结构关系图

查找表成员 type表示管理结构的类型；default_num表示与type对应的管理结构的数量；adr_offset保存着管理结构的地址。在该内存管理机制中，管理结构主要包括静态内存管理结构、动态内存管理结构和“类页面”管理结构。

2.2内存管理结构

动态内存管理结构和静态内存管理结构的共有属性memCommAttr与实体内存数据的关系如图3所示。

图3　内存管理结构共同属性

结构成员type指示该管理结构所管理内存的类型，next保存着同类型的内存管理结构的地址，memptr保存着该管理结构所管理的内存地址，size表示内存的容量。

我们以图3定义的内存管理结构为基础，设计了静态内存管理结构和动态内存管理结构。

图4　静态内存管理结构与静态内存空间的关系

静态内存管理结构包括它与动态内存管理的公共属性；num表示静态内存块的数量；count被用来记录静态内存块的分配情况。

为进一步提高节点内存利用率，我们实现了一种被称为“类内存交换”的功能。而为了兼顾内存的分配效率和内存的利用率，我们规定只有被划分为动态内存区的内存空间才支持“类内存交换”功能。

图5　动态内存管理结构

由图5可看出，动态内存管理结构就是由“类内存交换”结构和内存管理结构的共有属性构成。

2.3地址逆向映射

为实现内存数据与其对应内存管理结构的映射，我们在内存管理机制中设计了“内存逆向映射”机制。

图6　内存反向映射结构与动态内存空间的关系

地址逆向映射结构的成员type用来标识该内存的类型；id保存着该内存空间的区域id号，内存管理单元就是通过分配区域id号的方式实现了内存数据与内存管理结构关系的逆向映射；check保存的数据被用来进行用户操作的合法性检测，其值计算方式如式（1）。

2.4类页面

提高内存分配效率和降低内存管理复杂性，这也是该内存管理机制追求的目标。因此我们特定引入了“类页面［11］”功能，通过将节点内存按照系统预定义的大小划分为内存块，使得内存管理单元只需要保证其分配的id号在“类页面”内的局部唯一性，而且也使得内存管理单元能够快速而有效了解任意“类页面”中节点动态内存的分配情况。

图7　类页面管理结构

内存管理单元将“类页面”中的首个被系统分配的动态内存管理结构通过该next和prev成员组织起来。“类页面”管理结构成员occup和count分别表示页面中已被分配的内存大小和当前在类页面中存在的动态内存管理结构的数量。

2.5内存交换

为兼顾节点内存利用率和分配效率，节点的动态内存空间被设定为唯一支持“内存交换”机制的内存区域。

图8　内存交换结构

next和prev被内存管理单元用来保存“类页面”中被交换出数据的内存管理单元的地址，而动态内存交换结构的成员id和memptr被内存管理单元组合起来使用，用来标识当前内存数据被保存的位置，具体含义如表1所示。

表1　保存数据的位置或状态

3　系统运行流程

3.1节点内存初始化

节点内存管理单元进行初始化操作时，首先它从节点的非易失性存储器（Flash或EEPROM）的扇区中读取与节点内存配置相关的参数，其次依据读取的配置参数进行节点静态内存和动态内存空间的划分，最后分配静态内存块。

图9　初始化后系统静态内存分布

由于分配的静态内存容量是系统设计者考虑最坏的情形下，用户线程可能用到的内存容量，因此这种分配方式无疑会降低静态内存的利用率。为提高节点静态内存的利用率，我们将系统设定为在默认情况下系统只分配default_num一半数量的静态内存给用户，而在内存管理单元检测到静态内存的使用率达到系统阈值时，它将自动分配余下的静态内存空间。

3.2内存申请

内存管理单元为用户提供的内存分配接口为mmem_alloc，用户在使用该接口时必须提供两个参数：申请内存空间的容量与类型。由于节点的内存空间被内存管理单元划分为不同的类型，因此在分配不同类型的内存时，内存管理单元将执行不同的流程。3.2.1静态内存申请

用户程序向mem_alloc接口函数传递参数后，内存管理单元首先将进行传入参数的合法性检测。如果参数不合法，那么函数通过设置全局变量merrno指明内存分配失败的具体原因之后将自动返回；如果参数合法且还有未分配的静态内存，那么接口函数在完成相关静态内存管理结构的设置后将返回静态内存块的首地址。

图10　静态内存空间分配

接口函数对参数合法性的判定依据主要是检查用户程序传入的是否是系统预定义的type类型，同时检查静态内存管理结构是否支撑其申请的内存空间的容量size。如果同时满足上述两个条件，那么传入的参数合法，否则为非法。

3.2.2动态内存申请

由于节点的动态内存空间支持“内存交换”功能，所以当内存管理单元遇到无法分配足够的空闲动态内存时，它将激活系统的“内存交换”功能模块。该功能模块在完成内存交换之后，它将自动调用系统的内存分配函数。

图11　动态内存申请程序执行流程

3.3内存释放

内存管理单元为用户提供的内存释放的接口函数为mmem_free，用户在调用该接口时，必须提供需要释放的内存的地址。内存管理单元在接收到用户传递的内存地址后，将进行传入参数的合法性判定。如果参数合法且释放的内存空间地址属于动态内存空间，那么内存管理单元将依据“地址反射”机制查找与该内存空间对应的内存管理结构，然后通过对该结构进行操作完成内存的释放。

图12　内存释放流程

由于函数对参数合法性的判定将根据释放内存类型的不同而变化，所以接口函数在进行参数合法性判定之前，必须先进行内存类型的判定。接口函数的判定是通过比较参数address与指示静态内存区容量的变量memStaticSize的大小，如果address小于memStaticSize那么内存属于静态类型；如果address大于memStaticSize，那么内存属于动态类型。当释放的内存空间属于静态内存空间时，系统对于参数address合法性的判定依据是能否找到管理该空间的静态内存管理结构；当释放的内存空间属于动态内存空间时，式（2）的计算结果作为释放地址合法性的判定依据。

如果result为零，那么函数判定参数address合法，接口函数将继续进行内存的释放操作；如果result等于一个非零值，函数判定参数address非法，接口函数将在设置全局变量merror之后返回。

静态内存管理结构和动态内存管理结构属性的差异造成内存管理单元在执行内存释放时，对内存管理结构将执行差异化的操作，其具体体现在：

（1）静态内存释放：系统将内存管理结构中与释放内存地址对应的标志位置为无效即完成了静态内存的释放。

（2）动态内存释放：系统通过内存管理结构成员memptr和id的组合来判定内存数据的当前保存位置。如果数据保存在Flash，那么系统在完成Flash的擦除后，将把内存管理结构从类页面中删除；如果数据保存在节点动态内存区，那么系统直接从“类页面”中删除该内存管理结构之后。在完成动态内存的释放后，系统都会执行空闲动态内存的合并。

3.4内存交换

当前情况下，我们将“内存交换”机制的激活条件定为如下两种：

（1）内存管理单元检测到无线传感网络节点空闲的动态内存容量小于系统设定的阈值；

（2）内存管理单元执行动态内存分配时发现无法满足用户的需求。

当内存交换功能模块被激活时，它将按照系统预设的算法将内存数据保存到节点Flash中。而为了识别Flash中存储的内存数据，内存交换模块将把动态内存管理结构相关的type、memptr、id和check这四个成员与内存数据同时保存于节点Flash。由此也可看出，“内存交换”将涉及到两类操作：内存数据换出和换入，其实现算法如下：

Algorithm 1　Memory data swap out require_size←user_require_size largest_in_memory←0 for all empty_memory_space∈PAGES do s←get_max_empty_space（empty_memory_space）if|neighbor_space_mergeable（s）|！=0∧|merge_space_size（s）|＞require_size then largest_in_memory←memory_swap（s）return address_after_merge else largest_in_memory←s end if end for return null Algorithm 2　Memory data swap in sectors_type←type sectors_id←id sectors_memptr←memptr sectors_check←check for all sector∈SECTORS do s←get_sector_metadata（sector）if|extract_type（s）|=sectors_type∧|extract_id（s）|=sectors_id∧|extract_memptr（s）|=sectors_memptr∧|extract_check（s）|=check　then data_size←extract_size（s）data_address←extract_address（s）memory_address←memalloc（mem_dynamic，datasize）if|address|！=0 then data_swap_in（address，data_address，datasize）return 0 end if end if end for return-1

4　实验评估

整个内存管理机制的性能测试分为内存分配性能测试和内存利用率测试。由于该内存管理机制涉及Flash数据读写操作，因此我们测试平台的核心芯片采用具有DMA［15］功能的TI公司生产的CC2530F256。该芯片基于2.4 GHz IEEE 802.15.4、ZigBee和RF4CE上的一个片上系统解决方案，片上资源包括8 kbyte SRAM、256 kbyte片上Flash。为了方便对该内存管理机制性能的测试，我们使用该芯片的5 kbyte SRAM作为系统的内存管理区和10 kbyte Flash作为内存交换区。

4.1内存分配性能测试

内存分配性能测试主要是测试节点内存管理单元写数据的速率。为减小测量的误差，我们将系统写数据的时间定为系统执行100次相同操作的总共用时。由于节点的动态内存分配方案可能使得系统的“内存交换”功能被激活，而内存交换的用时与系统自身设计的本地数据存储方式和内存交换的算法有密切关系，因此我们将从总的测试用时中减去这部分额外操作的时间。

测试方法：我们利用系统随机函数，随机生成数值大小在特定范围内的数字，并将该数字作为向内存管理单元申请内存空间大小的依据。当系统无法满足的内存的申请需求时，测试结束。

图13　内存分配性能测试

4.2内存利用率测试

我们将内存利用率测试定义为：测试成功写入内存空间的数据量（包括被交换到Flash的数据）与整个内存容量的百分比。

图14　内存利用率测试

5　结论

本文介绍了一种基于链表的改进型内存管理机制，该机制通过隔离内存的数据空间和管理结构，实现了“内存交换”的目的。本设计需要改进的地方为设计更加有效的内存交换预测算法，该算法能够更准确的选择出将来一段时间内不会被用户线程使用的内存数据块。该内存管理方案为提高无线传感网络节点的内存利用率和外部内存碎片的问题提供了一种可行的解决方案。

［1］William Stallings.操作系统精髓与设计原理［M］.第7版.陈向群，陈渝，译.机械工业出版社，2012：210-264.

［2］朱升林.LwIP协议深度剖析与实战演练［M］.水利水电出版社，2012：205-226.

［3］Han C，Rengaswamy R K，Shea R.A Dynamic Operating System for Sensor Nodes［C］//MobiSys：Proceedings of the 3rd International Conference on Mobile Systems，Applications，and Services. New York：ACM Press，2005：163-176.

［4］Adam Dunkels，Björn Grönvall，Thiemo Voigt.Contiki-A Lightweight and Flexible Operating System for Tiny Networked Sensors［C］//29th Annual IEEE International Conference on Local Computer Networks.New York：IEEE，2004：455-462.

［5］Cheong E，Liebman J，Liu J.Tiny GALS：A Programming Model for Event-Driven Embedded Systems［C］//Proc of the 18th Annual ACM Symposium on Applied Computing（SAC'03）.New York：ACM Press，2003：698-704：126-128.

［6］Simpson Z B.State Machines：Cooperative Mini-Kernels with Yielding［C］//Computer Game Developer's Conference.Austin：1999.

［7］Kasten O，Römer K.Beyond Event Handlers：Programming Wireless Sensors with Attributed State Machines［C］//Proceedings of the 4th International Symposium on Information Processing in Sensor Networks.New York：IEEE Press，2005：768-772.

［8］Tsiftes Nicolas，Adam Dunkels，Zhitao He.Enabling Large-Scale Storage in Sensor Networks with the Coffee File System［C］//International Conference on Information Processing in Sensor Networks.San Francisco：IEEE Computer Society，2009：349-360.

［9］Dunkels A，Schmid O，Voigt T.Protothreads：Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems［C］//Proceedings of the 4th International Conference on Embedded Networked Sensor Systems.New York：ACM Press，2006：29-42.

［10］Adya A，Howell J，Theimer M.Cooperative Task Management Without Manual Stack Management［C］//Proceedings of the USENIX Annual Technical Conference.Monterey：2002.

［11］Shih E，Cho S，Nickes，et al.Physical Layer Driven Protocol and Algorithm Design for Energy-Efficient Wireless Sensor Networks［C］//Proceedings of ACM MobiCom.Rome：2001：272-286.

［12］田辉.基于IP的物联网架构技术与应用［M］.人民邮电出版社，2011：138-148

［13］操作系统设计与实现［M］.第3版.陈渝，谌卫军，译.电子工业出版社，2007：255-259.

［14］Welsh M，Mainland G.Programming Sensor Networks Using Abstract Regions［C］//Proc USENIX/ACM NSDI.San Francisco：2004：29-42.

［15］曹宗凯，胡晨，姚国良.DMA在内存间数据拷贝中的应用及其性能分析［J］.电子器件，2007（30）：311-317.

蒋林林（1989-），男，汉族，四川人，重庆邮电大学通信学院，硕士研究生，主要研究方向为无线传感器网络资源管理技术，David_Jiangll@foxmail.com；

刘峰（1987-），汉族，重庆人，工业和信息化部电信研究院西部分院，助理工程师，主要研究方向为物联网应用技术，liufeng@chinattl.com。

Research and Design on Memory Management Mechanism in Wireless Sensor Networks

JIANG Linlin1，LIU Feng2*
（1.Chongqing University of Posts and Telecommunications，Key Laboratory of Optical Communications and Networks，Chongqing 400065，China；2.West Institute of China Academy of Telecommunication Research，Chongqing 401336，China）

At present，the usage of the on-chip RAM of wireless sensor networks node is really very low，which has driven us to have designed an improved memory management mechanism based on linked list.In this mechanism，we assume that all the programs were developed under the event-driven model.After that，RAM memory of the node is divided into static and dynamic memory space.At the same time，we have imported the memory isolation technology，which separates the memory management structure and memory space in the memory entity.In this way，we have achieved the purpose of managing the memory.The function test shows that the average writing speed is 500 kbit/s，if we had opened the memory swap mechanism，the usage of the RAM can almost reach 80%.Ultimately，the memory management mechanism proposed by us is an efficient solution to improve memory usage.

wireless sensor networks；memory management；memory isolation；event-driven；memory swap

TP302.1

A

1005-9490（2016）05-1118-06

2015-10-07修改日期：2015-11-10

EEACC:6150P10.3969/j.issn.1005-9490.2016.05.020