Computer Science and Application计算机科学与应用, 2011, 1, 1-6 http://dx.doi.org/10.12677/csa.2011.11001 Published Online June 2011 (http://www.hanspub.org/journal/csa/) Copyright © 2011 Hanspub CSA The Wireless Energy-Saving Scanning Strategy Based on Vacation Queuing System Zhiqing Xiao1,2*, Yidong Cui1 1State Key Lab of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 2Wireless and Mobile Technology Research Center, Research Institude of Information Technology, Tsinghua University, Beijing Email: xzq.xiaozhiqing@gmail.com Received: Apr. 18th, 2011; revised: Apr. 26th, 2011; accepted: May 12th, 2011. Abstract: WLAN device, such as Bluetooth, on mobile terminal can be used to scan the surroundings to dis- cover other peers. However, with energy limitations, the scanning actions must be well arranged to reduce power consumption. This paper proposes an energy-saving strategy that turns on and off the Bluetooth device at a configured time. The scenario of Bluetooth scanning is modeled as an M/M/1 vacation queue with spe- cially impatient customers and startup expenses. In the M/M/1 queue, the terminal with Bluetooth device is the only server which scans its nearby customers, and the on-off state of Bluetooth device is indicated as va- cation behaviors. The aim of the paper is to find the best vacation strategy. Simulations demonstrated that the best strategy depends on the intended error rate, startup time and expenses and many other factors. The per- formance of the multiple vacation strategy is satisfactory on most conditions. Keywords: Energy-Saving; Vacation Queuing; Bluetooth; Environment Perception 基于休假排队系统的无线扫描节能策略 肖智清 1,2*,崔毅东 1 1北京邮电大学网络与交换技术国家重点实验室,北京 2清华大学信息技术研究院无线与移动通信技术研究中心,北京 Email: xzq.xiaozhiqing@gmail.com 收稿日期:2011 年4月18日;修回日期:2011 年4月26 日;录用日期:2011 年5月12 日 摘 要:在一些环境感知的应用中,移动终端的无线模块(如蓝牙)需扫描周围环境以发现其他设备。但 这种行为非常耗能。提出了通过间歇性开关蓝牙模块以降低平均能耗的方法。将移动终端扫描的过程描 述成一个具有启动时间费用和特殊不耐烦顾客的休假排队系统。在该排队系统中,扫描周围环境的设备 是服务员。节能扫描的算法旨在通过优化休假触发条件和休假结束条件,以在保证一定的扫描效果的情 况下耗能最小。仿真结果表明多重休假策略在大多数情况下能有效降低能耗。 关键词:节能;休假排队;蓝牙;环境感知 1. 引言 随着移动终端的普及,各种终端应用层出不穷。 当前,有许多应用基于终端内置的无线通讯设备,对 无线环境进行感知。一些基于 GPS、蜂窝基站位置等 技术的应用能够确定终端的地理位置,另一些基于 WiFi、蓝牙(Bluetooth)技术的应用能够发现周围对等 的终端,并主动与它们交流,如 MobiClique[1] 、 SniffMob[2]等。MobiClique 是一个利用无线移动交友 平台。该平台中的终端通过蓝牙不断扫描周围的环境 来寻找朋友及朋友的朋友。在文献[1]中进行了在稠密 肖智清等 基于休假排队系统的无线扫描节能策略 2 | adhoc 网络中的匹配实验,得到了在蓝牙设备总是开 启时的设备发现率和匹配成功率。SniffMob 是一个基 于WiFi 和蓝牙的数据交换网络。在 SniffMob系统中, 终端扫描周围 WiFi 和蓝牙环境,并结合图论查找最佳 的数据分享源[2]。文献[3]对移动终端随机扫描传输数 据的性能作了实际测试。它们都试图在随机条件下获 得最好的性能。文献[4 ]考虑到了一个固定的服务员等 待顾客进入系统的状况。但是,这些应用有一个共同 的缺点:它们会消耗大量的电能。目前,有一些项目 对环境感知的节能算法进行了研究。在 EnLoc 系统中, Ionut 等人提出了一种基于节能的定位方法。但是,他 们只是在系统结构方面进行调整,没有提出一种普适 的节能方案。 现在考虑这样的一个场景:一个移动终端使用蓝 牙扫描其附近的移动终端。一旦它发现一个同伴(比如 Jenny),这个移动终端能够与它交换地址本、收藏夹 等信息。蓝牙设备扫描和通信时,会消耗大量宝贵的 电量。如果一个终端不断的扫描,电池就很快被用尽。 这既干扰到了用户的正常使用,又降低了移动终端及 其电池的使用寿命。为了节约电量,则应该关闭蓝牙 设备。但是,如果蓝牙设备不再运行,那么它就不能 发现在它身旁经过的同伴。为了在保证有足够的概率 发现目标的情况下尽量少的消耗能量,本文提出了一 种通过间歇性开关蓝牙设备的节能方案。 近几年,排队论被广泛的应用于节能优化中[5]。 一个关于 Ad-hoc 网络的工程介绍了使用排队论分析 类似网络的方法。同时,许多关于有中断的排队论模 型的研究成果被发表[6]。文献[7]对当前休假排队系统 的数学研究方法进行了完整和详尽的描述,得到了很 多数值结果。但是,它们都不是基于下文中提到的特 殊不耐烦顾客的情形,也没有考虑到在能耗和匹配概 率间的折衷问题。 2. 具有特殊不耐烦顾客的 G/G/1 排队模型 现在考虑引言中描述的场景:这个系统包括一个 主要的移动终端(以下称为“服务员”),它扫描周围 环境,发现移动中的其他对等终端(以下称为“顾客”)。 发现对等终端后,服务员会和发现的终端交换信息。 在同一时刻,它只能与一个终端交换信息。所有的终 端都在移动。考虑到客户的相对速度矢量是客户绝对 速度矢量与服务员速度矢量之差,固定服务员的位置 并不会失去一般性。这时,假设服务员的扫描范围是 一个以 R为半径的圆。如图 1,客户 1、2和4在服务 员的通信范围内,客户 5在通信范围外。客户 3正在 进入扫描范围,客户 6正在移动出扫描范围。 这样的一个随机服务系统可以被刻画成 G/G/1 排 队系统。当一个新的移动终端(如图 1中的客户 3)进入 服务员的通信范围时,一个顾客进入系统排队。当一 个终端结束服务时,一个顾客离开系统出队。对于每 个客户,其服务时间是不同的。例如,如果一个服务 员希望其他人的通讯录,服务时间取决于通讯录的长 度。 在这个服务系统中,客户是“特别”不耐烦的。 客户被称为“特别”不耐烦是因为不但在队列中等待 的客户会不耐烦,在正在被服务的客户也会不耐烦(如 图2)。如图 1中的客户 6,无论它现在是否正在被服 务,它都以相同的速率离开系统。 在这个系统中主要有以下两个指标:一、有多少 移动终端成功匹配了;二、服务员需要消耗多少能量。 第一个因素用成功匹配率 m来表示。假设在时间 t 内,有 enter Nt 个顾客进入队伍, served Nt 个顾客 接受完服务离开系统。这时,有 miss enter NtN t served Nt 其平均匹配成功率为 1 served enter missed enter mENtN tm ENt Nt Figure 1. Mobile terminal searching surrounding environment 图1. 移动终端搜索周围环境 Copyright © 2011 Hanspub CSA 肖智清等 | 基于休假排队系统的无线扫描节能策略 Copyright © 2011 Hanspub CSA 3 排队系统可以被刻画成一个生灭过程。 Nt 对于一般的 G/G/1 排队系统而言,队长分布、忙 期分布等参量是很难获得的。这个系统的“特殊不耐 烦”性使得由这些参量导出的匹配成功率和平均耗能 值更难获得。我们只能在输入过程、服务时间、离开 过程都是泊松过程的情况下求出以上参量的理论值。 例如,假设顾客的到达流是参数为 的泊松过程,服 务时间是参数为 的负指数分布,所有的顾客以速率 离开系统。(如图 3) Figure 2. G/G/1 queueing model with special impatient customers 第二个因素用平均耗能 e来表征。蓝牙设备的能 耗大小取决于它是否在工作。如果服务员没有服务任 图2. 具有特殊不耐烦顾客的 G/G/1排队模型 为了求出这时候的成功匹配率为 ,要求队长分 布。假设 0 m k pt是t时刻队长 的分布。由状态转移图 可得: k 何终端,那么单位时间的能耗为单位时间闲期能耗。 否则,它需要更多的能耗。这可以用单位时间忙期能 耗 来表示。如果蓝牙设备一直开着,那么平均耗能 就是在一段时间忙期耗能与闲期耗能的加权平均,即 i e b e 01 d d pt pt t (1) 11 d1 d 1 kkk k pt ptk pt t kpt k (2) bb iib i 关闭,那么开关一次所需要的能量为 eEtete tt 。如果蓝牙设备需要打开和 open e,所需要的 时间为 open t。(启动和关闭均被联合起来 是因为开 启行为和 行为总是成对出现的。 )这时,平均耗能 指数就和开关次数有关。假设在一段很长的时间内, 蓝牙设备开关 次,其工作时总忙期长度 ,总闲期长度 ,休假总时间 时间)为 ,则平均耗能 考虑 ii Tt 为 关闭 open bb n Tt 括开启 open n v Topen n (不包 在稳态时,队长分布为: 1 11 1 kk kkk k jj pjj (3) 则 01 11 miss enterk k mENtNt k ()( bb iiopenopenb i vopenopen ETeTeneTT Tnt e)。 节能模型的优化目标,就是找到一种休假出发策略和 p 。为 了获得平均耗能 ,需要构造一个生灭过程 0 e tN 确 定该系统忙期的概率分布。过程 N 来 与 t t的 N区别 在于它的第一个状态是吸收的。在下列方程组中, 0 ddpt 就是忙期的概率密度。 休假结束策略,使得 m尽量大(或是足够大),并使 e尽 量小。 01 d d pt pt t (4) 3. 系统性能理论分析 3.1. 无休假情况 显然,为了达到最优的扫描效果,蓝牙设备需要 一直开启。这对应着服务员一直在岗的情况。这时 121 d2 d pt pt pt t (5) 11 d1 d 1 kkk k pt ptk pt t kpt k (6) , Figure 3. State transition diagram M/M/1 queueing model with special impatient customers 图3. 具有特殊不耐烦顾客的M/M/1 排队系统状态转移图 肖智清等 基于休假排队系统的无线扫描节能策略 4 | 闲期长度服从参数为 i t 的 这个 3.2. 输入过程、服务间隔、不耐烦过程的多样性 实际上,输入过程、服务间隔、不耐烦过程和扫 描方 上下 与客户在系统中停留时间的分布有 关。 关:如果要遍历客 户们 精确 可以根据对周围统计环境当前的统计状 况来 3.3. 休假排队的节能策略分析 通过间歇性的关闭蓝牙设备,可以减少服务员的 能耗 负指数分布。但是, 率m 方程很难求出解析解。 向图、时间、地点、人物、行为等很多因素有关。 输入过程和服务员所在的时间地点环境有关。在 班时间的输入流要明显大于半夜三更时候的输入 流,在单行道上的输入流要明显小于在十字交叉路口 处的输入流。而且,由于地理位置的复杂性,其输入 分布也不同。 不耐烦过程 客户在系统中停留的时间,与扫描范围、和客户 运动轨迹和相对运动速度有关。 服务用户需要的时间与业务有 的通讯录,那么服务时间大致和通讯率长度成正 比,服务时间分布取决于通信录的分布;如果要向客 户们广播一个消息,那么服务时间是一个确定的值。 从终端用户的动作结合用户的使用习惯还可以很 的估计这些过程的具体分布。一个用户每天都是 在同一时候、同一地点上班下班、吃饭睡觉,在执行 某一个特点动作时其外环境是大致相同的。带有加速 度传感器的移动终端(服务员)可以更加当前移动终端 的运动状况,从一个历史的统计结果中选出一个最接 近的输入过程、服务时间和不耐烦过程作为当前情况 的预测值。 另外,还 自适应的修正目前对各种过程参量的预测。试想, 如果很长时间一个终端都没发现,这往往意味着在未 来比较长的一段时间内不会有目标终端进入扫描圈。 如果这时候的输入强度预测值明显过大,应将其减小。 。如果蓝牙设备被关闭了,我们称其“在休假”。 一个在休假的服务员只会了解它放假前的系统情况。 所以,诸如N策略休假排队等依赖于外部触发的可控 排队策略是不可实现的。服务员重回岗位,涉及前文 提到的启动时间 open t和启动能耗 open e。对于某种特定 的休假策略 P,在同的参数下会有不同的成功匹配不 和平均耗能 e 。m 上文已经提及,我们要使 尽 可能大,平均耗能e 尽可能小。显然,m不会超过在 没有休假的情况下成功匹配率 0 m。但是由于启动能耗 的存在,e 在某些情况下会比无休假时的平均能耗 0 e 大。这时,系统的总体性能会比不休假时还要差,休 假策略失 。 目前有许多成熟的休假策略,如空竭休假和非空 竭休假,闸门服 效 务,有限服 Bern 休假策略 多 策 务, oulli , 务 重 略 休假策略,增量休假策略,阈值休假策略等等[8]。 不同种类的休假策略在触发条件和结束条件上都不相 同。虽然它们都用随机分解的方法来分析,但是分析 其附加随机变量需要用到不同的数学工具。这十分复 杂。所以,我们不一一从数学上来进行分析,我们采 用仿真的方法来获得定量的结果。 4. 不同分布下休假策略的仿真和优化 我们使用 MATLAB,通过对不同输入过程、 时间和不耐烦过程进行休假策略的仿真,来体现休假 服 的有效性和不同分布对休假策略和参数的影响。 第I种情况,就是3.1 节提到的M/M/1 排队系统。假 设顾客的到达流是参数为 3 的泊松过程。假设服务 时间是参数为 2 的负指数分布。所有的顾客离 开 系统的速率分布相同,假设速率为 20 这个 。 下面我们来考情况 II。如图 4,服务员利用全 向天线进行蓝牙通信,其扫描方向图是一 圆。 虑 个正 时 这 ,如果客户到达时间是一个泊松过程,那么客户进 入扫描范围和离开扫描范围的过程就不是泊松过程。 理由如下:假设各个客户的行走轨迹是有向直线,当 用户在圆内的弦上可被服务。客户轨迹的弦心距满足 一定分布(比如说是均匀分布),客户运动速度的大小 也满足一定分布(如均匀分布、截短高斯分布、三角分 布或者是莱斯分布等)。对于这种情况,我们使用以下 的仿真条件:服务员的扫描半径 10R,顾客出现的 间隔服从参数为 3 的负指数分布,成功完成服务需 要的时间服从参数为 2 的负指 布。客户相对 于服务员运动的满足下列规律:顾客的路径是直线, 这个路径的圆心距 d满足~10之间的均匀分布。客 户从同一个方向运动(由于圆的对称性,这样假设并不 失一般性),其运动方向垂心距,且运动速度v 满足 1.6A 数分 3 直于圆 ,0.6 的莱斯分布(速度大小大约在 Copyright © 2011 Hanspub CSA 肖智清等 基于休假排队系统的无线扫描节能策略5 | Figure 4. Simulation scene 图4. 仿真场景 Figure 5. Matching rate and average energy consumption varying with vacation time 图5. 匹配率和平均耗能随着休假时间变化图 泊松过 程更符合实际情况。 对于 1.5~2.5 之间)。这样的不耐烦分布比直接使用 这两种场景,单位时间闲期能耗均为 1 i e , 单位时间忙期能耗均为3 b e,启动时间为 2 open t , 启动 ,经 于情况 于情况 ,, 能耗均为 10 open e。 如果不采用休假策略过仿真可得对I, 00.835m, ;对 02.119e 休假(Exha 00.938m 0 e 空竭服务多重 是较好的策 2.252 。通过对多种休假策略的仿真和比较发现, ust multiple vocation, E-MV) 略。在多重休假中,一旦系统内无顾客, 服务员立刻开始一次长度为 v t的休假。如果结束一次 休假时系统中仍无顾客,就接续一个休假,直到某次 休假结束时系统中已有顾客等待。这时,服务员终止 休假并开始接待顾客。这一休假策略曾广泛应用于最 大限度地利用空闲时间设置辅助工作的各种场合。在 仿真中,每次休假时间 v t是一个固定不变的值。对于 不同的 v t,可以得到不同的 E MV v mt 和 E MV v et 。 仿真的结果如图 5它们的横轴表示休假时间 v t(不包含开关时间)。左图是在不同情况下成功匹配 。 率 E MV休假随着休假时间的变化情况。休假时间越 m Figure 6 . Average energy consum p ti o n v a r yi n g with matching rate (The two isolated points is the case with no vacations) 图6. 随匹配率变化所需要的平均耗能 (两个孤立点是 无休假的情况) 大,成功匹配率越小。在给定指标 E MV m的情况下, 可以根据本图对休假时间进行配置。右图是在不同情 况下平均耗能 E MV e随着休假时间的变化情况。休 假 间越大,平均耗能越小。在确定休假时间后,可以时 根据本图对平均耗能进行预测。 ~ E MVE MV me 图可以用来表示在保证匹配率 E MV m的情况下 要的最小所需 E MV e。它可以用来评价 系统的整体性能。从图 6可以看出,采用空竭服务多 重休假,能保证在匹配概率为原来一半的情况下,耗 能减少约为原来的一 在一种休假排队节能策略。 在保证匹配概率的情况下,有效减少移动 保证 半。 5. 结论 本文用有特殊不耐烦顾客的G/G/1 系统对无线扫 描场景进行了建模,提出了 该策略能够 终端的能耗。仿真结果表明,采用多重休假策略,能 在匹配概率为原来一半的情况下,耗能减少约为 原来的一半。 Copyright © 2011 Hanspub CSA 肖智清等 基于休假排队系统的无线扫描节能策略 6 | C. Phillips, H. Gonzales, et al. SniffMob: Inferring human contact patterns using wireless devices. In International s, Applications and Services, ime-Slot Adapting Algorithm 6: 102-102. 参考文献 (References) [1] A.-K. Pietilainen, E. Oliver, J. Lebrun, et al. MobiClique: Mid- dleware for Mobile Social Networking. In Proceedings of 2nd ACM SIGCOMM Workshop on Online Social Networks, 2009- 8. [2] E. Anderson, Conference on Mobile System 2009-6. [3] I. Constandache, S. Gaonkar, N. Sayler, et al. EnLoc: En- ergy-Efficient Localization for Mobile Phones. In Proceedings of IEEE INFOCOM, 2009-4. [4] M. F. Neuts, M. F. Ramalhoto. Service model in which the server is required to search for customers. Journal of Applied Probabil- ity, 1984, 2 1(1): 157-166. [5] S. F. Yin, Y. Yin. Shortest Queue T Based on Average Reaching Times. In Proceedings of Second International Conference on Intelligent Networks and Intelligent Systems, 2009: 417-420. [6] P. Kulkarni, M. Nazeeruddin, S. McClean, et al. Deploying Lightweight Queue Management for improving performance of Mobile Ad-hoc Networks. In International conference on Net- working and Services, 200 [7] N. Tian, Z. G. Zhang. Vacation Queueing Models—Theory and Applications. New York: Springer, 2006. [8] 田乃硕. 休假随 机服务系统[M]. 北京: 北京大学出版社, 2001. Copyright © 2011 Hanspub CSA |