一種上下文感知計算中的衝突消解方法
2023-05-12 17:51:26
專利名稱：一種上下文感知計算中的衝突消解方法
技術領域：
本發明涉及一種上下文感知計算的方法，具體涉及一種一種上下文感知 計算中的衝突消解方法。
背景技術：
包括掌上電腦、行動電話、PDA等行動裝置已經越來越多地進入人們的 生活。為了向用戶提供更高的服務質量，適應這些行動裝置的應用應該是上 下文感知的，它能夠在不受用戶幹預的情況下根據用戶的上下文信息調整應 用的操作。這需要應用定時的獲取、更新上下文信息，根據這些信息決定應 用的執行策略。研究人員通過多種途徑解決這一問題，提出了一系列的解決 方法，包括Want等人的Active Badge Location System ， context toolkit 以及gaia等。
在這些開發面向上下文應用的方法中， 一個重要的思路是將不同環境下 不同的執行代碼分離到多個程序片斷中，在程序運行時根據當前執行環境動 態選擇需要的代碼片斷。這種方法可以有效地增加應用開發的靈活性，達到 適應環境變化的目的。包括Cop， Olympas在內的很多編禾呈模型給出了將不同 環境下的代碼分離在多個片斷的方法，但是仍有一個問題需要解決，那就是 在定義不同環境下的執行代碼時，需要對環境加以界定(例如，指定溫度的 範圍或者用戶所處的位置範圍等等)。由於定義不同環境的出發點不同，很有 可能出現衝突的情況(CRISMA)， 一旦衝突產生，則系統無法按照用戶需求選 擇正確的執行代碼完成操作。因此，發生衝突時的選擇算法成為一個必須解決的問題。
發明內容
本發明的目的在於克服上述現有技術的缺點，提供了一種結合環境因素 優先級別，計算當前上下文環境對每種判別條件偏移度，並根據偏移度大小 選擇相應的執行策略的上下文感知計算中的衝突消解方法。
為達到上述目的，本發明採用的技術方案是-
1) 針對每一種選擇策略，計算其策略選擇中心；
2) 獲取當前上下文數值；
3) 如果上下文數值為數值型，則轉步驟4)，否則轉步驟5);
4) 計算當前上下文數值與每個策略的差值，命名為偏移度值，轉步驟6);
5) 根據Pos函數及Count函數，計算偏移度數值，轉步驟6);
6) 記錄兩個策略的偏移度數值，作為下一次計算持久係數的依據；
7) 根據上次記錄的偏移度數值，計算此次持久係數
persistence 二 persistence + (past0ffset2 _ pastOffsetl) / pastOffsetl 其中persistence為持久係數數值，past0ffsetl和past0ffset2為上一次 記錄的偏移度數值；
8) 根據持久係數計算新的偏移度數值；
9) 根據新得到的兩個策略所對應的偏移度數值選擇執行策略；
10) 執行選定的策略。
本發明的數值型偏移度值的計算步驟如下
偏移度函數offset, P * E -〉 R+
偏移度為當前環境值對於策略中所有環境聲明條目的偏移度的加權和， 其中，PieP， e。eE， P4包含m個聲明條目，記為entry (i) ， l〈=i<=m， offset (i)表示每一個環境聲明條目的偏移度
formula see original document page 7在上述公式中formula see original document page 7用於計算環境條目的選擇中心，
2
分母計算條目的選擇範圍，將每一個偏移度值按照其條目的比重進行加權即 可得到該策略的偏移度值；
若當前環境值在兩個策略中都處於其條目的選擇中心，故偏離度為0， 因此在(1)式中引入常數C，修正offset (i)的計算公式得到
formula see original document page 7
c是一個大於0的常數，通常取值為1。
枚舉類型的偏移度值的計算方法為首先需要在定義策略時，指定策略 中枚舉類型的條目的可能值列表，隨後通過將枚舉值映射到其位置的函數， 將所有對枚舉值得計算轉化為對其在列表中所處位置的計算，得出其偏移度 值，其具體步驟為；
定義如下兩個函數
Pos函數R*Entry-〉N，給出一個值在一個條目的可肯巨值列表中的位置； Count函數Entry-〉 N，給出策略中一個條目所包含的限定值個數；
formula see original document page 7
本發明的持久係數是一個介於0和1之間的實數，隨著互相衝突的若干策略的偏移度值變化而變化，並將影響加入偏移度計算結果中，以下是持久 係數的計算以及對偏移度影響的計算公式
offsetl = offset (value, policyl); 〃此次計算的策略1的偏移度 offset2 = offset (value, policy2); 〃此次計算的策略2的偏移度 persistence = persistence + (past0ffset2 _ pastOffsetl) / pastOffsetl;
〃上一次計算的策略1和策略2的偏移度，並據此計算持久係數
if (persistence 〈 0) persistence 二 0; 〃持久係數始終大於等於0
〃將持久係數影響添加在偏移度上
〃並記錄此次偏移度值
i f(past0ffset1〈past0ffset2)
pastOffsetl = offsetl;
past0ffset2 = offset2;
offsetl = offsetl氺(1 - persistence);
6lS6
pastOffsetl = offsetl; past0ffset2 二 offset2; offset2 = offset2氺(l- persistence)。 本發明通過計算策略偏移度解決衝突。該方法結合環境因素優先級別， 計算當前上下文環境對每種判別條件偏移度，並根據偏移度大小選擇相應的 執行策略。在此基礎上，考慮環境因素連續變化因素，引入持久係數，防止 環境在小範圍內頻繁變化造成策略選擇抖動的問題。
具體實施方式
在上下文感知計算中，應用需要根據不同的上下文環境選擇不同的執行 策略。這些策略可能會出現衝突，大多數解決方法採用優先級策略。
本發明提出偏移度算法對衝突進行消解，計算每個策略的選擇中心，當 衝突發生時，計算每個衝突的策略的選擇中心與當前上下文環境的偏移度， 並選擇偏移度最低的策略作為執行策略。為了避免環境在小範圍內抖動的現 象，算法引入了持久係數，使上一次選中的執行策略在本次計算中具有一定 優勢，從而減少抖動的現象。
具體過程如下-
為了更準確的對本發明進行描述，首先對衝突問題進行定義及形式化描述。
定義l:符號。在系統中所有能夠獲取到的環境信息稱為系統環境信息。
所有環境信息的名稱的集合成為EName，所有可能環境值的集合為E，每一種 環境信息的值的集合為V;當前環境下的環境值計為^(e^E)。服務的集合稱 為S。所有服務的配置的集合稱為C。服務S的所有策略的結合成為P(S)， 在不產生歧義的情況下簡記為P。
定義2:服務。服務是在上下文感知系統中，根據用戶的上下文環境動 態調整自身行為，為用戶提供信息的功能實體。服務包含服務代碼及其配置 文件，配置文件是一組策略的集合，每個策略對應一個環境聲明以及一個執 行標識。環境聲明用於指定該策略能夠生效的上下文環境，執行標識指導服 務針對這一上下文環境調整其服務方式，執行標識根據實現方式的不同可能 代表一個方法名稱、 一個參數值或者一個屬性值等等。
Service ::二 servicelmplement configuration
Configuration ::二policySetpolicySet policy policySet | policy policy : = context identity
定義3:環境聲明。策略中的環境聲明用於界定這個策略能夠生效的上 下文環境。每個環境聲明包含一組聲明條目，每個條目用於限定一種環境信 息，例如，"溫度在10至20攝氏度之間"是對溫度這一環境信息限定條目的 文字描述。環境聲明條目中值的類型可以是枚舉類型或者布爾值，也可以通 過指定一個範圍來定義，可能的例子包括location二high, power=true， temperature〉10等。每個環境聲明條目需要指定其在整個策略中的權重，同 時需要給出值的邊界(對於枚舉或布爾類型的值，需要給出所有可能值的列 表)。
Context : contextEntrySet
contextEntrySet : := corvtextEntry corrtextErvtrySet | corvtextErvtry contextEntry ::二 name operator value type weight bound type ::= Boolean | enumerate | number bound min max if type二number valueList if type=enumberate or boolean
定義4:評估函數evaluate: EName*E -〉V。得到某個指定名稱的上下文 信息值。
在環境聲明條目cEntry中的operator與value共同組成了對環境信息 的界定條件o cEntry. operator (cEntry. value, evaluate (e0， cEntry. name) 二tme意味著該條目滿足當前上下文環境。
定義5:適應性函數fit: P*E-〉 Boolean
Fit(p，e)= fit (entry (1), e)& fit (entry (2), e)& .. &fit(entry(n)， e)
Fit(entry(k)， e) = fit(entry (k)， evaluate (e， entry(k). name)) fit (entry (k)， v) = entry, operator (entry (k). value ， v) 定義6:適應策略集合adaptSet: C * E -〉 2P adaptSet(c， e) = adaptSet (pl， e) U adaptSet (pset/pl， e) adaptSet (p， e) = if fit(p，e) then {p} else空集 定義7:衝突。如果llad鄰tSet(C，e"l卜0說明配置中沒有滿足當前環 境的策略，=1說明只有一個滿足當前環境。〉1說明有兩個以上的策略滿足 當前環境，我們稱這種情況為衝突。此時系統需要使用衝突解決方法來選擇 執行策略。
1)上下文衝突的偏移度算法 偏移度函數offset。 P * E -> R+
偏移度為當前環境值對於策略中所有環境聲明條目的偏移度的加權和，
偏移度越高表明當前環境對於策略中定義的環境需求偏差越大。
其中，heP， e。eE， Pi包含m個聲明條目，記為entry(i)， K=i〈=m。
offset (i)表示每一個環境聲明條目的偏移度
(ew^r少_ / max+ ew^y — / min)
evaluate (e , entry.name).
—max— ewfry — /. min| =t o炎"j x『一 /(2)
(1)
在上述公式中J'm，e"^ j'min)用於計算環境條目的選擇中心， 分母計算條目的選擇範圍。將每一個偏移度值按照其條目的比重進行加權即 可得到該策略的偏移度值。
當前環境值在兩個策略中都處於其條目的選擇中心，故偏離度為0。因此在(1)式中引入常數C，修正off set (i)的計算公式得到
formula see original document page 12是一個大於0的常數，通常取值為1。
對於枚舉類型的上下文數值，給出在這種情況下的偏移度計算辦法。首 先需要在定義策略時，指定策略中枚舉類型的條目的可能值列表。隨後通過 將枚舉值映射到其位置的函數，將所有對枚舉值得計算轉化為對其在列表中 所處位置的計算，得出其偏移度。
定義如下兩個函數
Pos函數R*Entry-〉 N。給出一個值在一個條目的可能值列表中的位置 Count函數Entry-> N。給出策略中一個條目所包含的限定值個數。
pos(evaluate(entry.name)) — 二
2
l<=k〈=m
2)防止衝突選擇策略抖動
在使用偏移度算法時，在某些情況下，隨著上下文環境的變化，策略會 發生頻繁抖動的現象。究其原因，當在某一環境下發生衝突時，當前環境同 時滿足兩個策略的環境限定(Pl， P2屬於adaptSet (C， E))。如果某個環境 因素在一個小範圍波動，會導致計算偏移度時，兩個策略的偏移度值頻繁上 下交錯，從而策略選擇結果不斷變化，產生策略抖動現象，這有可能會降低 用戶的滿意度，因此需要對算法加以調整。
在計算偏移度時，算法引入持久係數這一變量。持久係數的作用是，在計 算偏移度時，降低上一次選中的策略的偏移度值，使其更有可能被再次選中，從而較少抖動發生的機率。
持久係數是一個介於0和1之間的實數，隨著互相衝突的若干策略的偏移 度值變化而變化，並將影響加入偏移度計算結果中。以下算法對持久係數的 計算以及對偏移度影響的計算公式的簡要描述。
offset 1 = offset (value, policyl); 〃此次計算的策略1的偏移度 offset2 = offset (value, policy2); 〃此次計算的策略2的偏移度 persistence 二 persistence + (past0ffset2 - pastOffsetl) / pastOffsetl;
〃上一次計算的策略1和策略2的偏移度，並據此計算持久係數
if (persistence < 0) persistence = 0; 〃持久係數始終大於等於0
〃將持久係數影響添加在偏移度上
〃並記錄此次偏移度值
if(past0ffsetl〈past0ffset2)
pastOffsetl = offsetl;
past0ffset2 = offset2;
offsetl 二 offsetl氺(1 _ persistence);
pastOffsetl = offsetl;
past0ffset2 = offset2;
offset2 = offset2氺(l- persistence); 持久係數體現了上一次計算的偏移度的差別程度，並且具有累積效應。持 久係數能夠有效地平衡環境的小範圍頻繁變化對策略選擇造成的影響。後一 次環境變化的幅度如果小於前一次變化幅度，持久係數可以消除這種變化帶來的策略切換，但如果第二次環境變化幅度過大或者環境持續向一個方向變 化，那麼持久係數會將這種變化傳遞給偏移度，進而進行策略的切換。 算法的詳細步驟如下
1) 針對每一種選擇策略，計算其策略選擇中心；
2) 獲取當前上下文數值；
3) 如果上下文數值為數值型，則轉步驟4)，否則轉步驟5);
4) 計算當前上下文數值與每個策略的差值，命名為偏移度值，轉步驟6);
5) 根據Pos函數及Count函數，計算偏移度數值，轉步驟6);
6) 記錄兩個策略的偏移度數值，作為下一次計算持久係數的依據；
7) 根據上次記錄的偏移度數值，計算此次持久係數
persistence = persistence + (past0ffset2 - pastOffsetl) / pastOffsetl 其中persistence為持久係數數值，past0ffsetl和past0ffset2為上一次 記錄的偏移度數f直；
8) 根據持久係數計算新的偏移度數值；
9) 根據新得到的兩個策略所對應的偏移度數值選擇執行策略；
10) 執行選定的策略。
權利要求
1、一種上下文感知計算中的衝突消解方法，其特徵在於1)針對每一種選擇策略，計算其策略選擇中心；2)獲取當前上下文數值；3)如果上下文數值為數值型，則轉步驟4)，否則轉步驟5)；4)計算當前上下文數值與每個策略的差值，命名為偏移度值，轉步驟6)；5)根據Pos函數及Count函數，計算偏移度數值，轉步驟6)；6)記錄兩個策略的偏移度數值，作為下一次計算持久係數的依據；7)根據上次記錄的偏移度數值，計算此次持久係數persistence＝persistence+(pastOffset2-pastOffset1)/pastOffset1其中persistence為持久係數數值，pastOffset1和pastOffset2為上一次記錄的偏移度數值；8)根據持久係數計算新的偏移度數值；9)根據新得到的兩個策略所對應的偏移度數值選擇執行策略；10)執行選定的策略。
2、 根據權利要求l所述的上下文感知計算中的衝突消解方法，其特徵在 於所說的數值型偏移度值的計算步驟如下偏移度函數offset, P * E -〉 R+偏移度為當前環境值對於策略中所有環境聲明條目的偏移度的加權和， 其中，PieP， e。eE， Pi包含m個聲明條目，記為entry(i) ， K:i〈二m， offset (i) 表示每一個環境聲明條目的偏移度formula see original document page 3(1)在上述公式中(e"^ — z''max+e"^_/'min)用於計算環境條目的選擇中心，2分母計算條目的選擇範圍，將每一個偏移度值按照其條目的比重進行加權即 可得到該策略的偏移度值；若當前環境值在兩個策略中都處於其條目的選擇中心，故偏離度為0， 因此在(1)式中引入常數C，修正offset (i)的計算公式得到evaluate (e0， entry .name).(e欣j _ z.. max+ e"^y—min)2+ C-C>0(1*)|ew^>>—,. max- —/. min| C是一個大於0的常數，通常取值為1。
3、根據權利要求l所述的上下文感知計算中的衝突消解方法，其特徵在 於所說的枚舉類型的偏移度值的計算方法為首先需要在定義策略時，指 定策略中枚舉類型的條目的可能值列表，隨後通過將枚舉值映射到其位置的 函數，將所有對枚舉值得計算轉化為對其在列表中所處位置的計算，得出其 偏移度值，其具體步驟為定義如下兩個函數Pos函數R*Entry->N，給出一個值在一個條目的可能值列表中的位置； Count函數Entry-〉 N，給出策略中一個條目所包含的限定值個數；formula see original document page 3
4、根據權利要求l所述的上下文感知計算中的衝突消解方法，其特徵在於所說的持久係數是一個介於0和1之間的實數，隨著互相衝突的若干策 略的偏移度值變化而變化，並將影響加入偏移度計算結果中，以下是持久系 數以及調整偏移度值的計算公式offsetl = offset (value, policyl); 〃此次計算的策略1的偏移度 offset2 = offset (value, policy2); 〃此次計算的策略2的偏移度 persistence = persistence + (past0ffset2 - pastOffsetl) / pastOffsetl;〃上一次計算的策略1和策略2的偏移度，並據此計算持久係數if (persistence 〈 0) persistence = 0: 〃持久係數始終大於等於0〃將持久係數影響添加在偏移度值上〃並記錄此次偏移度值i f(past0ffset1〈past0ffset2)past0ffsetl = offsetl;past0ffset2 = offset2;offsetl = offsetl氺(1 - persistence);past0ffsetl = offsetl; past0ffset2 = offset2; offset2 = offset2氺(1— persistence)。
全文摘要
一種上下文感知計算中的衝突消解方法，該方法計算每個策略的選擇中心，並計算發生衝突的每個策略在當前上下文環境下的偏移度。通過比較策略之間的偏移度值選擇執行策略，從而解決衝突的問題。為了避免上下文環境在小範圍內頻繁變化造成策略抖動的問題，算法還引入持久係數對偏移度計算進行了修正。
文檔編號G06F9/46GK101446907SQ200810236559
公開日2009年6月3日 申請日期2008年12月31日 優先權日2008年12月31日
發明者暉 何, 迪 侯, 明 李, 牛玉潔, 旻 郗, 勇 齊 申請人:西安交通大學