一种提高Ad Hoc网络节点能量效率的DPM模型

摘要：在节点能量有限的Ad Hoc网络中，如何延长节点电池寿命并提高能量效率是能量问题研究的关键之处。针对这一问题，提出了移动节点的动态策略管理(DPM)模型，并在模型中引入了随机优化控制策略以提高节点能量效率。然后应用概率模型检测技术将其建模为DTMCs，并使用PRISM对这一策略和DPM中另外两种常用预测策略进行了比较，结果表明这一优化策略对网络的拥塞、延时及可靠性影响较小，其总体节能效果优于上述两种预测策略。

关键词：Ad Hoc网络；动态策略管理；随机优化控制策略

中图分类号： TP393

文献标识码：A

0引言

在节点不断移动、拓扑动态变化、带宽受到限制的Ad Hoc网络中，移动节点大多使用电池供电，其电源有限且不易充电。部分节点电池耗尽不仅会导致这些节点不能工作，还有可能影响到整个网络的性能。因而提高能量效率是降低网络运行成本、提高系统可靠性的关键技术，已成为系统设计的目标之一[1~3]。

针对这一问题，可以在不同协议层采用不同机制来降低能量损耗。当前提高能量效率技术的研究主要集中在网络层和数据链路层，并通过计算机仿真模拟来实现。在网络层，可以使用能量路由协议[1,2]来减少功率损耗。在数据链路层，可在节点或节点组件空闲时将其转入休眠状态以减少能量消耗，DPM(Dynamic Power Management)正是基于这种思想而提出的。近年来，已有许多研究机构和企业对DPM进行了的研究。如Intel等公司推出的ACPI，应用DPM思想以简化对系统资源的管理，但它并没有提出具体的节能策略[1,4]。为了减少能量消耗，无线网络接口要尽可能地处于休眠状态，基于此提出了基于休眠模式的无线MAC层协议[3,5]。此外，Norman等人应用DPM对无线网络接口进行了分析，指出进一步研究方向是将节能策略应用于移动节点的多个主要耗能组件如硬盘、显示器等，以此来提高节能效率[2,6]。

DPM策略分为预测策略(也称启发式策略)和随机优化控制策略。预测策略不能对两种能量状态以上的复杂系统及多个交互组件进行建模。便携电脑上常用的“time out”就是一种简单的预测策略。随机优化控制策略基于数学模型，对多状态系统中组件使用情况的概率特征进行精确假设，从而可以建立更为准确的模型，得出能量消耗与系统性能之间的优化解，确定在何时执行何种状态切换来减少能量消耗[1,6,7]。

基于上述分析，本文提出了移动节点的DPM模型，并在模型中引入了随机优化控制(以下简称为优化)策略以提高节点能量效率。然后使用概率模型检测工具PRISM[8]对这一策略与DPM中另外两种常用预测策略进行了比较，结果表明这一策略的总体节能效果优于上述两种预测策略。

1移动节点的DPM模型

移动节点的DPM模型如图1所示，其组成如下：

(1) 向设备发送请求的服务请求者(Service Requester,SR)；

(2) 存储不能立即执行请求的服务请求队列(Service Request Queue,SRQ)；

(3) 服务各请求的服务提供者(Service Provider,SP)；

(4) 根据系统负载和优化策略向SP命令的能量管理器(Power Management,PM)。

PM根据系统负载情况(如SP的状态、SRQ中请求数目等)，按照所采用的优化策略向SP发出状态切换命令，SP则按照PM的命令对SRQ中请求队列进行相应处理。本模型中SR、SP分别为无线网络接口 (Wireless Network Interface Card, WNIC)和硬盘。

WNIC有4个状态，使用Lucent IEEE 802.11 WaveLan的相关数据[1]。初始时处于sleep状态，每隔一定时间进入idle状态，当访问其他节点的资源时，WNIC进入send状态，并向其他节点发送请求消息，随后进入等待响应的recv状态。

硬盘有5个状态，主要使用IBM TravelStar Vp disk driver的相关数据，见表1、表2[6,7]。只有在active状态时硬盘才能执行数据读写操作。在idle状态下，硬盘旋转而其中的一些电子组件已经关闭。idlelp状态与此相似，但能量消耗更少。stby和sleep状态分别对应于硬盘停止旋转和关闭状态。

2优化策略

上述模型的目标函数可描述为系统平均能量消耗最小，其约束条件为系统丢失请求的平均概率以及请求平均等待延时均不能太大，使用优化工具和MAPLE工具得出如表3所示优化策略[6,7]。为了便于比较，对两种常用预测策略即贪婪time out策略(目前许多电子设备、电脑操作系统中使用此策略)和延时time out策略进行了分析。在贪婪time out策略中，SP在处理完请求后进入idle状态，空闲一定时间后进入sleep状态，有请求到达就进入active状态。延时time out策略的不同之处在于进入sleep状态后，直到请求队列满时才进入active状态，因而减少了系统切换开销。

3优化策略的PRISM建模

请求到达事件和请求服务事件均可抽象为随机过程，并假设所有请求具有相同的优先级，SP按照先来先服务的方式处理SRQ中各请求。根据表1和表2，为模型选择1ms的单位时间，并建模为DTMCs。每一组件用PRISM的一个模块来表示，分别描述如下。

3.1PM模块

PM根据系统负载情况，按照所采用的策略向SP发出状态切换命令。不同约束下，PM的代码见表3。

3.2SP模块

SP中状态迁移及平均时间见表1和表2。对于迁移时间超过单位时间1ms的迁移，引入中间状态并假定消耗2.5W的能量。例如中间状态active_idlelp表示从active状态迁移到idlelp状态，其迁移时间为600ms。

SP的概率有限状态机如图2所示。当sp为idle状态时，若pm=0(发出进入active状态的命令)，则sp进入active状态；若pm=1(发出进入idle状态的命令)，则sp保持此状态；若pm=2(发出进入idlelp状态的命令)，因为这一迁移需要5ms，故sp先迁移到active_idlelp；类似地，若pm=3(发出进入stby状态的命令)或pm=4(发出进入sleep状态的命令)，sp则分别迁移到activestby状态和active_sleep状态。

3.3SR模块

本文中SR为WNIC。在Ad Hoc网络中，节点的频繁移动会使已建立的路由失效，因而不能对请求及时正确地响应，导致丢失请求，在此用p表示SR与其他节点通信成功的概率。其概率有限状态机如图3所示，SR在sleep状态下每隔tout进入idle状态，在另一tout内若收到其他节点的请求，则相继进入send和recv状态，否则进入sleep状态。在recv状态下，以概率p与其他节点通信成功，之后进入idle状态。

3.4SRQ模块

SRQ用于存储不能立即执行的请求。仅当SR为idle状态且SP为active状态时，请求队列才会减少；另一方面，仅当SR为req状态而SP不处于active状态时，请求队列才会增加。其代码在此略去。

4结果分析

假设网络面积为1B000m×1B000m，共有20个移动节点分布其中，并独立自由移动。用PRISM对表3中不同优化策略以及贪婪time out和延时time out策略进行验证，结果如下：

(1) 优化策略对网络拥塞的影响

这一影响可描述为在T时请求队列满的概率，其概率越小，网络拥塞的概率也越小。验证结果如图4所示，在T时请求队列满的概率随着时间的增加而增大；随着平均队列大小的增加(约束条件放松)而略有增大。与p=0.5相比，p=0.9时，WNIC与其他节点通信成功的概率更大，因而向硬盘发送请求和请求队列满的概率更大。

(2) 优化策略所产生的延时情况

这一情况可描述为在T时刻之前请求得到服务的概率，其概率越大延时越小，因而不会显著地降低网络的吞吐率。验证结果如图5所示，约束为2时，仅当队列满SP才进行服务，故概率为0。请求得到服务的概率随着T的增加而逐渐增大，随着平均队列大小的增加(约束条件放松)而趋于减小。

(3) 优化策略对系统可靠性的影响

这一影响可描述为在T时间内丢失N个请求的概率，其概率越小系统可靠性越高。图6中，随着T的增加，丢失请求的概率逐渐增大；丢失请求数目N越大，系统到达这一状态所需的运行时间越长。由图7可知，系统丢失请求达到N=80的概率随着平均队列大小的增加(约束条件放松)而增加，这是由于平均队列越大，系统处于sleep状态的概率更大，因而需要一定时间迁移到active状态，故丢失的概率增大。

(4) 各策略中系统平均能量消耗和平均请求丢失情况

节点能量效率可通过节点的平均能量消耗来衡量。节点所消耗的平均能量越小，其使用寿命越长，能量效率也越高。使用PRISM得出上述策略中SP在T时处于各状态的概率，相应地可以计算出平均概率，SR计算类似。对于上述两种预测策略，SP只有active、idle、sleep三种状态，只需对这三种状态进行计算。

对于优化策略，令pij表示约束条件i下(约束条件编号见表3)处于状态j的平均概率，Cj为状态j下所消耗的能量(见表1)。如p01表示约束为0.001时SP处于idle状态的平均概率，C1=1.5W。系统平均能量消耗C=∑pij×cj,其中i∈{0,1,2,3,4,5,6},j∈{0,1,3,6,9}。类似地可计算WNIC的能量消耗。

由表4可知，优化策略的平均能量消耗随着平均队列大小的增加(约束条件的放松)而减少。与两种预测策略相比，约束为2的优化策略的平均能量消耗明显较少。与其他策略相比，贪婪time out策略平均请求丢失概率较小。延时time out策略的平均请求丢失概率与约束为2的优化策略接近。

公告

据举报并查实，刊登在我刊2006年第9期(P2148-2149,2159)题为“PKI互操作性的一种新的信任模型”署名管强、朱云的文章，原系日本朝日大学博士生郭峥、奥山辙教授和加拿大魁北克大学Finley Marion教授合作，公开发表在Oct.23-28, 2005, ICAS & ICNS 05国际学术会议上的论文：A New Trust Model for PKI Interoperability的中文译文。管强、朱云在未经得原论文作者同意就将其翻译成中文，也未告知编辑部，而以自撰论文名义发表该文，实属剽窃、抄袭他人论文、欺骗编辑部和读者的不端行为。这种行为严重违反了中华人民共和国著作权法，侵害了原著作权人的权利。本刊对这种剽窃、抄袭他人论文和欺骗他人的恶劣行为表示强烈谴责。本刊已通报侵权人所在单位，并责成其作出严肃处理。通知侵权人必须向受侵害人赔礼道歉，消除影响，退还不当得利。侵权人管强、朱云已承认剽窃事实并表示道歉。在不知晓该文是剽窃、翻译文章而刊登了此文，本刊向原英文论文作者及收录原英文论文的电子工程协会学术论文数据库、电气电子工程协会―计算机协会数字图书馆致歉。请收录本刊的各中文数据库将“PKI互操作性的一种新的信任模型”一文从相关数据库中撤出。本刊并通报相关期刊社，将在三年内不再收录刊登有涉嫌剽窃、抄袭的不端行为人的文章。

特此公告！

计算机应用杂志社

2007年4月10日