普適計算環境下上下文不一致性的消除算法研究
2009-01-01 00:00:00鄭笛朱珊
計算機應用研究 2009年1期
(1.海軍工程大學 計算機系， 武漢 430033; 2.解放軍第201醫院 財務中心，遼寧 遼陽 111000)
摘 要：在普適計算環境下，由于所獲得上下文信息的不一致性，往往會導致應用不一致性的產生。針對上下文不一致性的消除問題，提出了全丟棄消除算法、最新上下文丟棄算法、基于確定性上下文丟棄算法和基于相關性的上下文丟棄算法，并對算法的性能進行了比較和分析。實驗表明，這些算法能夠有效達到消除上下文不一致性的目的。
關鍵詞：普適計算； 上下文； 不一致性
中圖分類號：TP311.5 文獻標志碼：A
文章編號：10013695(2009)01015203
Research ofalgorithms for elimination ofinconsistent
context in pervasive computing
ZHENG Di1， ZHU Shan2
(1.Dept.of Computer， Naval University of Engineering， Wuhan 430033， China; 2.Financial Center， PLA 201th Hospital， Liaoyang Liaoning 111000， China)
Abstract:To resolve the context inconsistency， this paper put forward several resolution algorithms which discarded all the inconsistency contexts， the latest contexts， the contexts with the lower certainty and the contexts with lower frequency respectively. According tests prove the inconsistency can be resolved effectively.
Key words：pervasive computing; context; inconsistency
0 引言
隨著嵌入式技術的深入發展和應用，與PC有著相同計算能力的便攜移動設備層出不窮，智能掌上計算機、PDA(personal digital assistant，個人數字助理)和智能手機便是其中的典型代表，它們具有微型化、智能化和嵌入化的特點。另一方面，無線網絡技術的出現和應用為計算設備的互連帶來了非常大的便利，推動了計算模式新的變革。因此，普適計算[1~3]的計算模式和理念孕育而生，并且已經滲透到人們的生活和工作中。普適計算將人們從以設備為中心的計算模式帶入到以人為中心的計算模式，已成為當前計算模式發展的潮流，成為學術界和工業界研究的熱點和焦點。在普適計算環境中，用戶會連續不斷地與不同的計算設備進行隱性交互。在這個交互過程中，計算系統實際上是根據與用戶任務相關的位置、動作、歷史記錄等上下文信息提供服務的。這些上下文信息起源于進行數據采集或測量并將其表示出來的服務，反映了與對象相關的屬性信息，它能夠改變顯示給用戶的信息、用戶的選擇、用戶發布命令的效果，以及預測下一步最有可能發生的事件等。上下文感知是系統自動地對上下文信息、上下文信息的變化以及上下文信息的歷史進行感知和應用，并根據其調整自身的行為，是提高計算智能性的重要途徑，也是智能系統與周圍環境之間方便、高效的交互方法。通過有效地利用上下文信息來模擬人類在潛意識的交互，上下文感知計算將使應用具備智能感知、啟動和執行的特點，使應用更人性化，也更方便人們的使用。因此，隨著普適計算技術的發展，上下文感知技術正成為實現普適計算目標的關鍵性技術之一。
上下文感知系統感知的上下文信息通常來自于不同的物理傳感器，但由于傳感器的易錯性，所產生的上下文信息的質量無法得到有效的保證，其中一個重要的方面就是不一致性上下文的產生。所謂不一致上下文是指系統中的上下文存在矛盾，它出現的重要原因是上下文感知系統常常假設傳感器采集的數據是理想的、精確的，推理規則是絕對合理并且全面的，但這些條件在實際中往往不能滿足。現有的上下文感知系統研究往往集中在不一致性上下文的檢測，對不一致上下文的消除并沒有進行系統的研究，因此針對不一致性上下文的消除，提出了全丟棄消除算法、最新上下文丟棄算法、基于確定性上下文丟棄算法和基于相關性上下文丟棄算法，并對算法的性能進行了比較和分析。
1 上下文不一致問題的產生
普適計算環境中存在大量的計算與通信設備，這些設備能夠有效地增加人類的思維和行動。普適計算環境中的應用通常是上下文感知的，使用不同種類的上下文，如位置和時間可以對演化的環境進行適配，并提供靈活的服務。例如，用戶的手機如果能夠感知用戶的位置，在用戶欣賞音樂會時將會以振動的方式提醒用戶，而不是以通常情況下的響鈴方式。在普適計算中，上下文信息通常是用于描述事件發生時的環境或形態（用戶當前的位置和活動）。當上下文信息中沒有矛盾時，則保持了上下文一致性，否則說明上下文發生了不一致。例如，張三是一個教師，他隨身攜帶一個PDA來安排日常的事務。不同種類的上下文信息，如張三正在工作的環境、張三所處的房間、張三負責的學生的狀況都可能會影響到PDA對張三下一行為的建議。假設在某一時間，PDA從不同來源獲得三個上下文片段：a)張三在教室（用戶的位置）；b)一堂課程正在3504教室進行（房間狀態）；c)張三正在翻閱書籍（用戶的活動）。
從a）和b）可能能夠得出張三正在進行一堂課程的結論，基于前面所獲得的信息，3504房間是教室。然而，從c）可能會得出另一個結論，張三并沒有正在授課，因此能夠立即去別的教室。這兩個相反的評估反映了當前上下文中的矛盾，或者說對周圍環境的一個矛盾理解。因此，PDA可能會難以決定是否向張三傳遞命令去別處檢查學生的課堂狀況還是將請求傳遞給其他教師。最終，系統可能不能正常工作。
上下文不一致性的發生可能有大量的原因。在上面的場景中，它可能是因為不準確的位置檢測（如張三是路過而非位于教室）或不正確的活動推理（如張三在教室中活動或聽課，而非他那一時刻正在授課），而在現實生活中，因為推理資源的缺乏，上下文不一致性經常發生。研究表明，上下文的不一致性往往來源于上下文自然存在的不恰當性：
a)高動態的環境使得上下文容易廢棄。例如快速移動物體的位置上下文（沖向教室的教師）容易導致錯誤的位置上下文的獲取與產生。
b)上下文可能是由不同標準下的異構來源所提供的。不同的感知技術和標準可能導致語義上沖突的上下文（如靠近門但分別處于房間里和房間外的情況）。
c)推理可能由于計算資源的限制而獲得不準確的信息。實時響應的需求（如時間限制）可能導致在推理高層上下文如用戶的活動時對可用上下文的部分考慮。
d)網絡連接的斷開或錯誤而導致不完整的上下文。計算的移動性增加了上下文丟失的可能性（如張三和李四走進某間教室，變成張三走進教室）。
這些不恰當來源的存在使上下文的不一致性成為了一個普遍現象，要在普適計算環境下保證上下文的正確性、完整性和非冗余性是非常困難的。
2 不一致上下文的消除
要消除不一致性上下文，首先要檢測到不一致上下文的發生。現有的研究中，有多種不同的上下文檢測算法[4~6]，通過這些不一致性檢測算法，能夠有效地檢測到沖突的上下文。接下來面對的一個問題就是上下文不一致性的消除，簡單地說，就是沖突上下文的清除。對于不一致上下文的清除來說，可以有多種不同的沖突上下文清除方法。在本章中提出了全丟棄、最新上下文丟棄、基于確定性上下文丟棄和基于相關性上下文丟棄幾種不一致性消除算法，并對算法的性能和正確率以及對于上下文感知應用的影響進行了比較和分析。
2.1 全丟棄不一致性消除算法
對于檢測出的沖突上下文，要通過刪除相應的上下文來消除不一致性。所謂全丟棄不一致性消除是最為直觀的不一致性消除方法，即將產生沖突的上下文實例不加區分地完全刪除。如算法1所示為全丟棄不一致性消除算法。
算法1 全丟棄不一致性消除
a）等待匹配隊列中任何新的上下文實例；
b）對所有的檢測模式；
c）在觸發器中；
d）if檢測到不一致性；
e）thendelete 所有沖突的上下文實例；
f）通過定時控制線程的定時器將未沖突的上下文實例加入上下文池中。
全丟棄不一致性消除算法具有實現簡單的優點，但對于大多數上下文感知應用來說，由于傳感器所獲得的上下文錯誤率或沖突率甚至可能高達40%以上，使用全丟棄不一致性消除算法將導致大量的上下文信息遺失，從而最終影響到上下文感知應用的性能。
2.2 最新上下文丟棄不一致性消除算法
相對于最新上下文丟棄不一致性消除算法來說，最新上下文丟棄不一致性消除并不是丟棄所有發生沖突的上下文，因為很多沖突的發生是由于新進入的上下文實例和已有的上下文實例之間的沖突，甚至這部分已有的上下文實例可能即將加入上下文池進行存儲。通過對上下文實例的開始時間進行比較，能夠判定上下文實例的新舊程度。如算法2所示為最新上下文丟棄不一致性消除算法。
算法2 最新上下文丟棄不一致性消除
a）等待匹配隊列中任何新的上下文實例；
b）對所有其他的模式；
c）在觸發器中；
d）if檢測到不一致性；
e）then比較沖突上下文實例的開始時間和更新時間；
f）delete較新的上下文實例；
g）通過定時控制線程的定時器將未沖突的上下文實例加入上下文池中。
最新上下文丟棄不一致性消除算法相對全丟棄不一致性算法來說保留了更多的上下文實例，從而為上下文感知應用保留了更多的有用信息，但同時對上下文實例時間域的比較將在一定程度上降低算法的效率，并且在某些情況下最新的上下文實例可能恰好是最為正確的上下文信息，因此本算法可能會增加上下文感知應用出錯的可能性。
2.3 基于確定性上下文丟棄不一致性消除算法
最新上下文丟棄不一致性消除算法存在最新的上下文實例可能恰好是最為正確的上下文信息的情況，從而可能會增加上下文感知應用出錯的可能性。因此可以通過對確定性的比較保留確定性較高的上下文。如算法3所示為基于確定性上下文丟棄不一致性消除算法。
算法3 基于確定性上下文丟棄不一致性消除
a）等待匹配隊列中任何新的上下文實例；
b）對所有其他的模式；
c）在觸發器中；
d）if 檢測到不一致性；
e）then比較沖突上下文實例的確定性域；
f）判定確定性最高的上下文實例；
g）delete確定性較低的上下文實例；
h）通過定時控制線程的定時器將未沖突的上下文實例加入上下文池中。
基于確定性上下文丟棄不一致性消除算法相對最新上下文丟棄算法具有更高的準確性，同時相對全丟棄不一致性消除算法能夠為應用保留更多的上下文信息。但基于確定性的上下文丟棄算法需要對每個上下文實例進行確定性的判定和比較，從而會加大算法的額外開銷，降低算法的效率。
2.4 基于相關性上下文丟棄不一致性消除算法
基于確定性上下文丟棄需要對每個上下文實例進行確定性的判定和比較，從而會加大算法的額外開銷，降低算法的效率。同時，對于不同種類的上下文來說，不確定性的判定更為復雜。因此對于不同的上下文來說，考慮這些上下文的頻繁程度，因為更頻繁的原始上下文比不頻繁的那些具有更高的優先級，也可能是正確的上下文。然而，要為不同種類的上下文比較頻率是非常困難的。例如，噪聲上下文可能會比溫度上下文更為頻繁地變化，但是不能說噪聲上下文具有更高的優先級。因為這個原因，使用相對頻率來為每一個原始上下文進行度量，具有更大的相對頻率值的上下文近來更為頻繁，它們更可能是正確的上下文。當沖突發生時，丟棄具有較小的相對頻率值的上下文。
式（1）為計算原始上下文的相對頻率的方法：
contexti rf=contexti#8226;period×contexti#8226;freshnesscurrenttime-contexti#8226;starttime（動態上下文）∞（持久上下文）
（1）
如算法4所示為基于相關性上下文丟棄不一致性消除算法。
算法4 基于相關性上下文丟棄不一致性消除不一致性觸發線程
a）等待匹配隊列中任何新的上下文實例；
b）對所有其他的模式；
c）在觸發器中；
d）if 檢測到不一致性；
e）then比較沖突上下文實例的相關性；
f）判定相關性最高的上下文實例；
g）delete 相關性較低的上下文實例；
h）通過定時控制線程的定時器將未沖突的上下文實例加入上下文池中。
基于相關性上下文丟棄不一致性消除算法相對最新上下文丟棄算法具有更高的準確性，同時相對全丟棄不一致性消除算法能夠為應用保留更多的上下文信息。并且基于相關性的上下文丟棄不一致性消除算法能適用于不同類別的上下文，具有更好的通用性。
2.5 性能測試
圖1中，對全丟棄、最新上下文丟棄、基于確定性上下文丟棄和基于相關性上下文丟棄幾種不一致性消除算法的作用進行了比較和分析。
實驗中共使用三臺計算機，即一個4 GB RAM和 2 Xeon CPUs的工作站以及兩個通過局域網互聯的PC客戶端，一個客戶端負責充當原始上下文的提供者，而另一個則充當上下文的消費者。在實驗中為了簡化對上下文信息正確性的分析，只使用了兩種類型的傳感器。需要指出的是，在這個實驗中盡管只使用了兩種類型的傳感器，但本文的體系結構和算法能夠不作任何修改地適用于更多的傳感器類型，因為它們針對語義上下文設計，而非物理傳感器。當引入新的傳感器類型時，惟一需要做的就是增加特定的原始上下文提供者。
從圖2中可以看出，基于確定性和基于相關性的不一致性消除算法具有更好的性能，同時在工作站上對上述算法的性能進行了比較和分析，可以發現隨著內存中總的上下文的增加，算法的效率將會相應地下降。如圖2，以基于相關性的丟棄算法為例，當緩沖區上下文實例為1 000~2 000時，使用的時間為1.5~2.0 s，而在上下文實例為3 000~4 000時，需要6 s。同時全丟棄和最新丟棄算法相對來說具有較低的不一致性處理時間，而基于確定性的丟棄算法由于需要對上下文實例的確定性進行判定，具有相對最高的處理時間。
本文對幾種不同算法的錯誤率進行了比較。為了進行比較，將三個不同的應用分別運行600次（總共30個大循環，每個循環20次），并記錄了每一次循環的錯誤率。在實驗中，所有被記錄下來的錯誤是應用得不協調的行為，而系統的錯誤，如內存溢出等則不加以考慮。從實驗結果中同樣可以看出，隨著正確性概率的提高，各上下文不一致性管理機制能夠在不同程度上提高上下文感知應用的健壯性，由于大量的上下文沖突所產生的不協調的行為被減少，從而提高了上下文感知應用的性能。
3 結束語
事實上，對于上下文不一致性的檢測和消除來說，只是對進入的沖突上下文進行處理，并保證上下文池中所存儲的上下文的一致性，但并不關心對上下文來源的修正，因此環境將依然產生不一致的上下文，從而在一定程度上造成不一致性檢測的重復。現有的大多數傳感器設備和軟件程序都能夠支持對它們生命周期的直接控制，使其能夠停止產生上下文或在必要時在稍晚的時間重啟，并且能夠通過改變算法的參數（如位置相關算法）來調整錯誤率和不確定性。因此，在今后的研究工作中，當完成上下文檢測和不一致性消除后，將對上下文來源給出一定的反饋機制，從而使傳感設備能夠進行一定的調整，以提高上下文處理的效率，避免錯誤上下文信息的重復產生。
參考文獻：
［1］WEISER M. Computer for the 21st century[J]. Scientific American， 1991，261(30):94104.
［2］徐光裕，史元春，謝偉凱. 普適計算[J]. 計算機學報， 2003，26(9)：10421050.
［3］鄭增威，吳朝暉.普適計算綜述[J].計算機科學，2003，30(4):1822.
［4］XU C， CHEUNG S C，CHAN W K. Incremental consistency checking for pervasive context[C]//Proc of the 28th International Conference on Software Engineering(ICSE 2006). 2006:292301.
［5］XU C， CHEUNG S C. Inconsistency detection and resolution for contextaware middleware support[C]//Proc of the 10th European Software Engineering Conference and the 13th ACM SIGSOFT Symposium on Foundations of Software Engineering (ESEC/FSE 2005). 2005:336345.
［6］LI J， BU Y， CHEN S， et al. Followme: on research of pluggable infrastructure for context awareness[C]//Proc of the 20th International Conference on Advanced Information Networking and Applications (AINA2006). 2006:199204.
［7］HENRICKSEN K， INDULSKA J， RAKOTONIRAINY A.Modeling context information in pervasive computing systems[C]//Proc of the 1st International Conference on Pervasive Computing. 2002: 167180.
