無線傳感網絡節點內存管理機制的研究與設計

蔣林林，劉　峰

（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