基于进程代数的上下文感知模型

基于进程代数的上下文感知模型 Vol . 39 ?10第 39 卷 第 10 期西安交通大学学报 2005 年 10 月Oct . 2005 J O U RN AL O F XI′A N J IA O TO N G U N IV ER SI T Y 基于进程代数的上下文感知模型 1 ,2 1 1 ,2 1达王卫红, 覃 征, 曹玉辉, 李 ()1 . 西安交通大学电子与信息学院 , 710049 , 西安 ; 2 . 河北经贸大学信息技术学院 , 050000 , 石家庄 摘要 : 针对当前上下文感知研究大多集中于技术解决 ,缺乏理论上统一描述模型的问 ,提出了基于进 ( ) 程代数的上下文感知模型 CA MB PA. 该模型独立于具体的应用平台 ,具有平台无关性 . 首先 ,利用带时间 参量的上下文的状态变迁来描述动态环境的变化 ,并根据进程代数的合并理论 ,采用合成简单环境状态变迁 的方法来实现对复杂环境状态变迁的描述 . 随后 ,通过在模型中引入感知函数 ,实现了对感知行为的描述 ,同 时对上下文状态变迁赋予了资源语义 ,从而使模型能够刻画移动计算环境中的动态资源情形 . 采用染色 Pe2 t ri 网对 CA MB PA 模型实例进行了可视化仿真 ,结果明该模型具有语法 、语义的正确性 ,以及良好的可扩 展性 ,能够很好地描述上下文感知. 关键词 : 移动计算 ;上下文感知 ;进程代数 ;染色 Pet ri 网 () 中图分类号 : T P393 文献标识码 : A 文章编号 : 0253Ο987 X 200510Ο1060Ο04 Context2A wareness Model Ba sed on Process2Algebra 1 , 2 1 1 , 2 1W a n g W ei hon g , Q i n Z he n g , Cao Y u h u i , L i D a ( 11 School of Elect ro nics and Info r matio n Engi neeri ng , Xi′a n J iao to ng U niver sit y , Xi′a n 710049 , Chi na ; 21 College of Info r matio n )a nd Technolo gy , Hebei U niver sit y of Eco no mics a nd Bu si ne ss , Shijiazhua ng 050000 , Chi na Abstract : In o r der to sol ve t he p ro ble m t hat t he mo st of t he cur re nt re sea rche s o n co nt e xt2awa re ne ss fo2 cu sed o n t he t ec h nolo gy sol utio n a nd lac ked unified de scrip tio n mo del t heo reticall y , a no vel mo del ba sed o n co nt e xt2awa re ne ss , CA MB PA , wa s p ropo sed. The mo del i s i ndep e nde nt of t he sp ecific app licatio n p lat2 fo r m . Ma ki ng u se of t he st at e t ra n sitio n of co nt e xt wit h ti me p a ra met e r , it de scri be s t he dyna mic e nvi ro n2 me nt c ha nge s. A nd acco r di ng to t he p roce ss2al ge bra co mbi natio n t heo r y , it i mp le me nt s t he de scrip tio n of t he co mp le x e nvi ro n me nt by synt he sizi ng si mp le e nvi ro nme nt st at e s. Thro ugh a ddi ng a n awa re ne ss f u nc2 tio n to t he mo del , t he awa re ne ss be ha vio r wa s e xp re ssed . A t t he sa me ti me , t he sp ecific re so urce se ma n2 tic s wa s give n to t he co nt e xt st at e t ra n sitio n , t herefo re t he mo del depict t he dyna mic re so urce sit uatio n i n t he mo bile co mp ut atio n e nvi ro nme nt . A CA MB PA i n st a nce i s si mulat ed vi suall y by u si ng colo r Pet ri net . The re sult s i ndicat e t hat t he mo del ha s co r rect gra mma r a nd e xact se ma ntic defi nitio n , a s well a s f a vo ra ble e xp a n si bilit y , a nd ca n p erf ect l y de scri be t he co nt e xt2awa re ne ss. Key words : m obi l e com p ut i n g ; conte x tΟa w a re ness ; p rocessΟal g eb r a ; col o r Pet ri net 随着无线通信技术的发展和移动设备的普及 ,上下文感知在自适应移动和有效屏蔽设备的移 人们实现了在任何时间 、任何地点访问网络上的任 ,已有许多人为此做了大 动性方面具有重要的作用 [ 128 ] 何信息. 如何屏蔽设备的移动性 ,使网络的频繁断接 量的工作,但目前的相关研究多数集中于技术解 对用户透明 ,已成为移动计算领域需要解决的热点 决方案上 . 在实际应用中 ,不同类型的上下文需用不 证明 由定理 1 和定义 3 可证得 .,其相应的数据 表达模型有符号化模型和几何模型 σσ结构为键Ο值对 、标记编码 、对象等 ,它们都是面向具 定义 4 设是一个动态环境状态 , 具体的由相应 的 [ 3 ] 体应用的. 目前 ,多数的系统仍没有用统一的理论 上下文取值状态确定 . 若 LΑ′ L 不包含矛盾命题 ( ) σ即对所有的 A ?P , A | L或′ A | L′, 则在 L 下′ 的 模型来描述上下文 ,或对变化的上下文进行感知 ,这 σσ状态变迁可定义为一个新的环境状态. L′, 记为 ,′ 并称就使得在各种上下文感知的应用平台之间进行交互 σσσσ为′的一个变迁可达状态 , L为′的′变 比较困难 ,严重阻碍了上下文感知的有效应用. 本文 迁集.针对这种上下文感知理论模型的不足 ,提出了基于 σσ需要说明的是 , 从到的′变迁往往不止一个 变进程代数对上下文感知进行建模的方法 ,对上下文 感知进行了更高级别的抽象 ,并通过该方法建立了 迁集. 因此 , 当环境状态发生状态变迁时 , 总会有 ( ) 基于进程代数的上下文感知模型 CA MB PA. 一个最小变迁集 Lσσ, 在这个最小变迁集中 , 只需包 ,′含 取值状态发生变化的上下文即可 . 1 CA MB PA 模型 定理 2 设 L , L ?L , 如果 L ?L 不包含矛盾命 1 2 1 2 11 1 进程代数 题 , 那么 ( ) 进程代数 Proce ss Al ge bra , PA 是一种形式化 (σ) σ. L . L = . L ?L 1 2 1 2 的描述复杂系统的建模工具 ,它以代数形式来描述 ( ) σ如果 L 1 ?L 2 包含矛盾命题 , 那么 . L 1 ?L 2 没有 模型 ,并为模型化系统定义了一套完整的语法和语 定义.义 . 有关进程代数的起源 、发展及其形成的若干问题 σσ证明 由定义 4 可知 , 状态 在 L 下的变迁为 . L 1 分别在文献 [ 9 ,10 ]中有所论述 . σσσ, 则. L 为新状态 , 将新状态记为;′ 状态再在′ L 下的1 1 2 基于进程代数描述的特点在于 : ?概念简单且 σ变迁为.′ L . 若 L ?L 不包含矛盾命题 , 一定有状2 1 2 描述能力强 ; ?可通过简单环境复合出复杂环境 ,尤 σ( ) σ态在 L ?L 下的变迁为 . L ?L ; 若 L ?L 1 2 1 2 1 2 其是对移动计算这种复杂的动态环境 ,可实现全局 ( ) σ包含矛盾命题 , 则. L ?L 是无定义1 2 环境建模 . 的 . 故 , 定理 2 得证.CA MB PA 可以通过对带时间标记的上下文状 引理 2 环境状态在一组命题集合下的状态变迁 ,态变迁的描述 ,来反映动态环境的变化 ;通过对上下 相当于这个环境状态依次按每一个命题进行变迁 .文状态变迁语义的定义 ,来刻画移动计算环境中的 证明 由定义 4 与定理 2 可证得 .动态资源 . σσ定义 5 设1 ?2 , 当 L 1 , L 2 ?L 且当 L 1 ?L 2 不包 11 2 相关定义及定理 σσσσ含矛盾命题时 , 称1 和2 是可合成的 , 记为1 32 定义 1 在移动环境中 , 所有的上下文集合为 C , 则 σ( ) =. L ?L .C = { c, , c, , c} . 1 2 1 i n C 到其值集合 V = { nu mber , a b st ract }的映定理 3 环境状态发生复杂状态变化 , 可以通过一 定义 2 射为 F : C ?V , 其中 nu mbe r 可以是数值型数据 、数系列简单状态变迁的合成来描述 . 值区间或数值型枚举集 ,这需要根据特定上下文的 证明 由定义 5 和引理 2 可证得 .具体情况确定 ,而 a b st ract 是字符串型数据 , 可以是 定义 6 设动态环境中感知环境上下文变化的实体 相关上下文的摘要信息 .为 E , 则 定理 1 对于所有的命题 A , 如果 ϖ A 满足 A 是 c δΛμψ)(iE = ,,, ) ( 到其值集合 F c的一个描述 , 那么 A 的逻辑值可 i δΛ 式中 :为 E 所需的环境资源 ;为 E 的所有可能的以表征上下文 c 的取值状态 .i ΛΛΛμΛ 行为集 ,= {1 , ,,,v } ;为 E 的行为发生 i 证明 由定义 1 和定义 2 可证得 .μμμμψ 条件集或称为行为规则集 ,= {1 , ,,,} ; j l 定义 3对 于所 有 的命 题 A 的 集合 为 P ,则 P = ψφμφφ为感知函数 ,: ?,为系统对 E 的作用函数 ,: { Π A | A , A 是一个命题集合} . P 及其非的集合记为 L ? E 可反映环境状态变化对实体的影响. L , 则 11 3 CAMBPA 模型 L = P ? P = { A , A ?A ? P} ( σ综上所述 , CA MB PA 模型可用一个元组 T ,, 「 φ) L , E ,来 描 述 , 其 中 T 为 离 散 时 间 的 序 列 , T = 描′P引理 1 设 t 时刻的命题集合为 P,′ P′Α P , 则 , , t, { t, tn } , ti ?T . 述了一组确定的上下文取值状态 .1 i 「 「 设在 t时 刻 , CA MB PA 模 型 处 于 一 个 格 局i ΘΘt , 若 在 ti + 1 时 刻 , 模 型 格 局 发 生 变 化 , 即 t ? i i Θ σσt, 此 时 环 境 状 态 变 化 为 t ?t , 变 迁 集 为 i + 1 i i + 1 φψLσ σ , 相应有 : Lσ , σ ? E , E 将通过感知到 , tt tt ii + 1 ii + 1 μΛ环境的变化 , 从而根据产生一个. 感知行为表现出的行为复杂性 , 反映了系统状 态变化的复杂性 , 而不是智能主体自身结构的复杂 性 . 2 CA MB PA 下的染色 Pet ri 网的 可视化仿真验证 图 2 仿真任务处理流程图 21 1 仿真平台及原理 ( ) 染色 Pet ri 网 C PN 是一种适用于系统设计 、 [ 11 ] 描述 、模拟和验证的面向图形的建模语言, 提供 了验证设想和检验一致性的途径. 仿真实验平台为 [ 12 ] C PN Tool s, 是编辑 、模拟和分析染色 Pet ri 网的 工具. 设 c为 C PU 资源上下文 , 记为 x , c为内存资 1 2 源上下文 , 记为 z , c为磁盘空间上下文 , 记为 y , c3 4 为网络带宽上下文 , 记为 w , 则上下文的集合为 C ={ x , z , y , w } . 相应的值集 V 均为数值型数据 . 为了验证结果 St a rt : 仿真开始 ;Loadi ng :仿真初始化 ; Re so urce : 上下文所 的普遍性 , 各个上下文的取值均为实时动态数据 . 当 描述的动态环境资源 ; Co mp a re : 资源判定函数 ; Relea se :环境上下文取值状态发生变化时 , 其状态变迁映射 执行状态结束 ; End :仿真结束为库所间的变迁. 图 3 仿真结果示意图仿真时 , 设定一个初始时刻 t, t的环境上下文 0 0 状态可作为仿真模型的系统输入 , 经仿真任务处理 后 , 即可得到仿真输出. 仿真框架示意如图 1 所示. 仿真任务处理流程如图 2 所示 . 图 1 仿真框架示意图 21 2 仿真结果 仿真结果如图 3 所示. 模型中的位置集合 、参变量等元素采用 C PN 标 ( ) 记语言 ML 描述 , C PN ML 的语法描述如图 4 所 示 .图 4 C PN ML 的语法描述 仿真结果表明 , CA MB PA 模型具有语法 、语义形 . [ 6 ] A bo wd G D , Dey A K , Bro w n P J , et al . To war ds a 息的自适应需求 , 实现屏蔽移动性. bet ter under sta nding of co ntext and co ntext2awa rene ss 本文针对目前上下文感知研究中缺乏统一理论 [ A ] . 1 st Inter natio nal Sympo sium o n Handheld and 模型的问题 , 提出了 CA MB PA , 并将该模型应用于 U biquito us Co mp uting , Karl sr uhe , Ger many , 1999 . 移动嵌入式电子商务平台 , 解决了基于上下文感知[ 7 ] Pet relli D , No t E , St rappa rava C , et al . Mo delling 的移动自适应问题 . 目前 “, 移动嵌入式电子商务平 co ntext i s like ta king pict ures [ A ] . Wo r k shop o n Co n2 台”一期工作已通过验收和评定 , 并获国家教育部科 text Awarene ss , Hague , Net herlands , 2000 . 技进步二等奖. 今后的研究工作主要包括 :进一步完 Chal mer s D. Co ntext ual mediatio n to suppo rt ubiqui2 [ 8 ] 善该模型 ; 实现该模型的理论性验证 .to us co mp uting [ D ] . Lo ndo n : Facult y of Engineering , The U niver sit y of Lo ndo n , 2002 . 参考文献 :[ 9 ] Baeten J C M . A brief hi sto r y of p roce ss algebra [ R ] . Repo rt CSR , 04202 . Eindho ven , Net herla nds : Va k2 [ 1 ] Ducha mp D. Issue s in wirele ss mo bile co mp uting [ A ] . groep Info r matica , Techni sche U niver sit eit Eindho ven , 3 r d IE E E Wo r k shop o n Wo r kstatio n Op erating Sys2 tems , Key Bi scayne , U SA , 1992 . 2004 . [ 10 ] Cero ne A . Fro m p rocess al gebra to vi sual la nguage [ 2 ] Wei ser M . So me co mp uter science i ssues i n ubiquito us [ A ] . The Co nf erence o n Applicatio n a nd Theo ry of co mp uting [ J ] . Co mmunicatio ns of t he A CM , 1993 , () Pet ri Net s , A delaide , A ust ralia , 2002 . 36 7:74Ο83 . [ 11 ] CPN Gro up of U niver sit y of Aa r hus of Denmar k . [ 3 ] Schilit B N , A da ms N , Want R. Co ntext2aware co m2 CPN Tool s [ EB/ OL ] . ht tp :/ / wiki . daimi . a u. dk/ cp n2 p uti ng applicatio ns [ A ] . IE E E Wo r k shop o n Mo bile tool s/ cp ntool s. wi ki , 2004Ο08Ο11 . Applicatio ns , Santa Cr uz , Co mp uting Systems and [ 12 ] J ensen K. Colo ured Pet ri net s : a high level la nguage U SA , 1994 . fo r system a nd analysi s [ A ] . L ect ure No tes in Co m2 Bro w n P J , Bo vey J D , Chen X. Co ntext2aware appli2 [ 4 ] p uter Science [ C ] . Berlin : Sp ringer2Verlag , 1987 . 248 catio ns : f ro m t he labo rato r y to t he ma r ketplace [ J ] . () Ο299 . IE E E Per so nal Co mmunicatio ns , 1997 ,4 5:58Ο64 . [ 5 ] Tur ner R M . Co ntext2mediated behavio r fo r intelligent () 编辑 苗 凌agent s [J ] . Inter natio nal J o ur nal of H uma n2Co mp uter () St udie s , 1998 , 48 3:307Ο330 . ()上接第 1055 页 [ 4 ] [ 3 ] co de [ J ] . IE E E Trans o n Circuit s System fo r Video TM5、TMN8等码率控制方案的控制效率 ,并且 () Technolo gy , 1994 , 3 10: 509Ο517 . 也可以用在新一代图像编码 J P E G2000 中 ,为 Hoa ng D T , L inzer E L , Vit ter J S. L exico grap hic bit [ 6 ] 不同的图像子带分配目标比特数 . allocatio n fo r M P E G video [ J ] . J o ur nal of Vi sual Co mmunicatio n a nd Image Rep re sentatio n , 1997 , 8 参考文献 : () 4: 384Ο404 . [ 1 ] Co ver T M , Tho ma s J A . Element s of info r matio n Choi J , Pa r k D. A sta ble f eedback co nt rol of t he Buff2 [ 7 ] t heo r y [ M ] . New Yo r k : Wiley , 1991 . er state using t he co nt rolled L agrange multiplier met h2 L ee H J , Chia ng T , Zha ng Y Q . Scala ble rate co nt rol [ 2 ] o d [ J ] . IE E E Trans o n Image Proce ssi ng , 1994 , 3 fo r M P E G24 video [ J ] . IE E E Tra ns o n Circuit s Sys2 () 9: 546Ο557 . () tem fo r Video Technolo gy , 2000 , 10 9: 878Ο894 . Vap nik V N . The nat ure of stati stical lea r ning t heo r y [ 8 ] [ 3 ] J o r di R C , L ei S. Rate co nt rol in DC T video co ding fo r [ M ] . New Yo r k : Sp ri nger2Verlag , 1995 . lo w2delay co mmunicatio ns [ J ] . IE E E Tra ns o n Cir2 Nertavali A N , Ha skell B G. Digital pict ure : rep re2 [ 9 ] ( ) cuit s System fo r Video Technolo gy , 1999 , 9 1: 172Ο sent atio n a nd co mp re ssio n [ M ] . New Yo r k : Plenum , 185 . 1998 . ISO2IEC/ J TC/ SC29/ W G11 , Te st mo del 5 [ S ] . 1993 . [ 4 ] () 编辑 刘 杨Wa ng L . Bit rate co nt rol fo r hybrid D PCM/ DC T video [ 5 ]