物聯網中適用于內容搜索的實體狀態匹配預測方法

張普寧劉元安 吳 帆 唐碧華 吳 超

（北京郵電大學智慧無線移動信息技術中心 北京 100876）

物聯網中適用于內容搜索的實體狀態匹配預測方法

張普寧*劉元安 吳 帆 唐碧華 吳 超

（北京郵電大學智慧無線移動信息技術中心 北京 100876）

對實體匹配用戶內容搜索的狀態進行預測可顯著提高物聯網搜索的效率，降低搜索過程的通信開銷。該文提出等時距與周期內實體狀態預測方法，估計實體在用戶查詢時刻的狀態；設計了適用于內容搜索的有序驗證方法，依據實體匹配用戶查詢內容的概率對實體進行排序驗證，以保證用戶搜索結果的可靠性。結果表明，所提實體狀態預測方法具有較高的精度，結合所提預測方法與匹配驗證方法的搜索機制具有較低的通信開銷。

物聯網；內容搜索；狀態預測；匹配驗證

1 引言

面對物聯網中海量、多樣化的物理實體，如何快速、準確地搜索用戶需要的物理實體是物聯網搜索服務需解決的根本問題［1］。傳統的搜索引擎主要用于搜索網頁及pdf， doc文件等靜態或緩變的非結構化內容，而物聯網中數據具有較強的時空特性，其建立的索引為爬取時刻的內容［2］，無法即時呈現物理實體的實時狀態。因此，如何設計高效的物聯網實體搜索機制是物聯網中的關鍵性問題。

目前，國內外針對物聯網實體搜索的研究剛剛起步。文獻［3， 4］對物聯網搜索服務的內容、特點和典型系統以及物聯網搜索技術面臨的挑戰和發展趨勢進行了概括。為避免物聯網搜索過程中信息資源泛濫，降低搜索過程中的通信開銷，文獻［5］設計了Dyser搜索引擎，將傳感器與物理實體的狀態信息均抽象為Web網頁，并提出可估計實體周期性狀態的預測模型。通過計算實體頁面與搜索內容匹配的概率，獲得可能匹配搜索請求的物理實體的集合。然而，文中基于傳感器節點可獲取實體的周期性高級狀態的假設。因此，上述搜索機制對采用低成本傳感器且實體狀態轉換周期性不顯著的應用場景適用性較差。

針對上述問題，文獻［6］提出支持基于內容的搜索機制（CSS），利用傳感器的原始輸出時間序列歷史數據構建實體狀態預測模型，估計實體與查詢內容匹配的概率，以搜索與用戶需求匹配概率較高的傳感器。然而，CSS的實體狀態估計方法具有時間獨立性，忽略了物聯網中實體狀態隨時間動態變化的特性，未準確感知實體狀態的動態變化趨勢，造成對實體狀態的估計精度較差，從而給物聯網的實體搜索過程帶來較多的通信開銷。

為解決上述問題，本文提出適用于物聯網內容搜索的實體狀態匹配預測（Entity State Matching Prediction， ESMP）方法，通過傳感器采集的實體狀態歷史記錄構建實體狀態預測模型，預測實體在用戶查詢時刻的狀態，并結合用戶提交的查詢內容，提出實體狀態匹配估計方法，估計實體與用戶查詢內容的匹配概率，進而，依據匹配概率進行實體狀態的有序匹配驗證，以降低搜索過程中的通信開銷。

2 物聯網內容搜索服務架構

本文所提ESMP搜索服務架構如圖1所示。用戶通過客戶端發出內容搜索請求；物聯網網關負責搜索請求的下發及傳感器上報數據的收集；預測模型數據庫用于存儲傳感器上報的歷史數據與預測模型；傳感器用于采集實體狀態數據，實體為最終的搜索對象。

物聯網搜索系統中有多個物聯網網關分布在Internet中，每個網關負責一個或多個傳感器網絡，并與該傳感器網絡的預測模型數據庫關聯。物聯網網關通過周期性地爬取傳感器發布的web頁面來獲取傳感器當前的讀數，并將讀數存入預測模型數據庫中用來構建實體狀態的預測模型。

客戶端通過GUI界面發起搜索請求，用戶請求首先由上層網關進行處理，按照地理位置等具有區分度的信息進行分類，并下發到下層網關進行內容查詢的搜索。由于物聯網中實體的狀態具有時變性，用戶查詢具體的狀態值的實用價值較小，因此，物聯網中搜索的形式如：表示搜索在tq時刻溫度在 aoC～ boC 之間的實體， Rq為用戶定義的需返回的匹配實體個數。

下層網關在接收到上層網關下發的搜索命令后，將訪問本地的預測模型數據庫，搜索匹配概率較高的傳感器，并將實體匹配排序列表及其匹配概率發送給上層網關，上層網關將接收到的排序列表進行匯聚，并依據匹配概率進行排名，進而，對排名靠前的實體進行逐一驗證，以確定實體是否真正滿足用戶的查詢需求。最后，網關將經過驗證的搜索結果返回給用戶。

3 實體狀態預測方法

為保證搜索結果的時效性與可靠性，使得搜索過程快速收斂，本節通過利用傳感器周期性上報的實體狀態信息，建立可預測實體在下一個周期內任意時刻狀態的預測模型，在用戶發起基于內容的搜索請求后快速決策用戶所需實體。

3.1 實體等時距狀態預測方法

圖1 ESMP搜索架構

（1）實體狀態時間序列矩陣變換：為構建預測模型，需對傳感器采集的時間序列進行重構，將實體狀態時間序列轉化為可最大化時間序列相關性的矩陣形式。通過滑動時間窗口 χt= ［x（ t） ，…，x（t + m- 1）］， t =1，2，…， nt-m 控制訓練樣本的輸入。其中 x（t + i）為第（t + i）個周期傳感器采集的實體狀態值， nt為訓練集的大小。 yt= x（t + m）表示實體在第 t個周期的實際狀態值，也為預測模型的期望輸出值。則 yt與 χt滿足映射關系 f:Rm→ R。變換后的訓練集矩陣如式（1），式（2）所示：

（2）實體等時距狀態預測模型構建：物聯網中傳感器所采集的實體狀態數據具有非線性、隨機性等特點，為減少傳感器采集數據的存儲開銷，降低實體狀態預測的計算復雜度，本文基于最小二乘支持向量機（LSSVM）［7］提出實體等時距狀態估計（Equal-interval Entity State Prediction， E-ESP）方法，進行等時間距離下實體狀態的預測。

為實現傳感器采集的實體狀態數據線性可分，需構造最優線性回歸函數 f（x）：

式中，φ （ x）: Rn→ H為非線性映射函數；w ∈H為特征空間中的權值向量；b為偏移量。

為提高所提實體狀態預測方法的泛化能力，根據結構風險最小化（Structural Risk Minimization，SRM）準則，將最小二乘支持向量機表述為

其中，J為耗費函數； γ＞ 0表示懲罰系數；ei為偏差值。通過拉格朗日函數將其轉化為非約束優化問題，從而得到該問題的對偶形式：

式（5）中 αi為拉格朗日乘子。根據KKT條件并消去權值w和偏差值 ei后，則可得到對應的矩陣方程

采用最小二乘法求解式（6）中參數b與α，可推得實體狀態預測函數 y（x）為

為降低所提實體狀態預測方法的計算復雜度，本文選用廣泛采用的高斯徑向基（RBF）核函數：

則實體狀態預測函數 y（x）可進一步轉化為

3.2 實體周期內狀態估計方法

前述預測模型可預測實體等時間距離的狀態值。然而，用戶發起內容搜索請求的時間具有較強的隨機性。因此，本文進一步提出周期內實體狀態的估計（During the Period Entity State Prediction，DPESP）方法，對周期內的實體狀態進行估計，以滿足用戶在周期內的搜索需求。

為提高實體狀態預測模型的精度，本文采用牛頓插值多項式［8］對實體周期內的狀態進行預測。假設給定的實體狀態樣本點集為ti表示用戶查詢的時刻，為用戶查詢時刻的實體狀態值。定義 x（t）關于t0與 t1時刻實體狀態的一階均差］為

同理可得 x（t）關于 t0， t1與 t2時刻的二階均差則 x（t）關于 （t0，t1，…，時刻的實體狀態n階均差為

由于實體狀態 x（t）關于 t0與 t1時刻的二階均差，因此，可將進一步轉化為

將式（14）代入式（13）中可得到實體在t時刻的狀態 x（t）為

由此，可進一步獲得預測多項式 fn（t）為

周期內實體狀態預測多項式 fn（t）構建完成后將開始對實體在當前周期內的狀態進行預測。為保證用戶得到搜索結果的可靠性，網關將進行選定實體狀態的驗證。

為充分利用驗證過程的實體狀態信息，提高實體狀態預測方法的精度，本文進一步提出利用驗證數據的周期內實體狀態估計（During the Period Entity State Predictionwith Verification Data， DPESP-VD）方法，將用戶的查詢時間 tq及被選定驗證的實體狀態值x（tq）作為樣本點代入預測多項式中，對 SNT進行更新：

4 實體有序驗證方法

通過前述建立的預測模型，網關可估計實體的狀態與用戶搜索的內容是否匹配，然而，實體狀態的匹配程度尚缺乏統一的度量指標。并且，為保證搜索結果的可靠性，網關需對實體的實際狀態作進一步驗證，而逐一驗證的方式將極大地增加系統的通信開銷，影響搜索結果的時效性。因此，本文提出實體有序驗證方法，由網關按照匹配排序列表依次對實體的狀態進行驗證。

4.1 實體匹配排序方法

為便于比較實體之間的匹配概率，估計實體狀態與用戶搜索內容的匹配程度，本文提出實體狀態匹配排序方法，將實體狀態預測值映射到向量空間中進行度量。假定實體在 ti時刻的狀態預測值為（ti），則將（ti）映射入向量空間中并轉化為如式（18）形式：

4.2 實體匹配驗證方法

為保證搜索結果的可靠性，需選定匹配實體并對其進行驗證。本部分提出實體匹配驗證方法，依據實體匹配排序列表ML對排名靠前的實體的實際狀態進行驗證。

如前所述，下層網關在獲取本地實體匹配排序列表ML后，將該列表發布給上層網關，由上層網關對下層網關的多個排序列表進行融合處理，從而得到驗證列表融合決策規則為

其中MLi為下層網關 i上報的排序列表，δ為上層網關發布的驗證次數，函數 MAX｛·｝為獲取列表中具有最大匹配概率的節點。定義 Rq為用戶指定的需返回的搜索結果數量，則δ與 Rq滿足式（21），式（22）：

5 仿真驗證與結果分析

本文采用Intel Berkeley數據集［9］對所提方法進行仿真驗證。查詢范圍［a， b］為區間內的隨機值。 xMin與 xMax分別為所有傳感器讀數的最小值與最大值，查詢時間 tq為［0， ω］內的隨機值。計算機仿真軟件環境為Matlab R2014a，仿真結果均為運行20次后的平均值。

5.1 實體等時距狀態預測方法性能驗證

本節對E-ESP與典型的等時距實體狀態預測算法GM-ESP［10］進行了對比，仿真結果如圖2所示。

圖2 不同誤差容忍閾值下的成功率對比

由圖2可知，E-ESP及GM-ESP的預測成功率隨閾值的增大都呈現出顯著上升趨勢。E-ESP較GM-ESP在預測成功率方面平均提高了約7.6%。其中在 γ= 0.2時，E-ESP的預測成功率可達到96.7%，在誤差閾值較小時即達到了較高的精度。所提E-ESP算法通過將數據轉換至矩陣空間中，從而增強實體狀態數據之間的時間相關性，并采用LSSVM 模型進行實體等時距狀態的單步預測。因此，相比GM-ESP， E-ESP在預測成功率方面有較大幅度的性能提升。

5.2 周期內實體狀態預測方法性能驗證

本部分驗證了所提周期內實體狀態預測方法（DPESP）的性能，并與利用驗證數據的周期內實體狀態預測方法（DPESP-VD）進行了對比，仿真結果如圖3所示。

由圖3可知，隨著查詢次數的增多DPESP-VD方法的預測精度呈現上升趨勢，而DPESP并未呈現出明顯的變化趨勢。兩種周期內實體狀態預測方法均具有較高的精度，其中DPESP-VD較DPESP在預測精度方面有一定提升。DPESP-VD方法合理利用了匹配驗證過程中的歷史數據，適用于所需預測精度較高的應用場景中，而 DPESP方法未利用歷史數據，適用于網關的存儲空間受限的場景中。

5.3 實體匹配預測的搜索方法有效性驗證

本節驗證了融合所提實體匹配預測方法的搜索機制的有效性。由于所設計的搜索機制包括實體有序驗證環節，因此用戶總是得到符合搜索要求的實體列表，則搜索過程中的通信開銷就只與實體的驗證列表相關。因而，定義搜索過程的歸一化通信開銷co（VLq）為

由圖4可知，隨著單個周期內查詢次數的增多，所提 ESMP算法的通信開銷呈現出顯著的下降趨勢，而CSS算法的趨勢則并不明顯。ESMP的通信開銷相比CSS平均降低了約30.6%，較CSS算法有較大幅度的提升。

如圖5所示，ESMP算法的通信開銷隨運行時間的延長保持了相對穩定的趨勢，充分說明了ESMP方法具有較好的泛化能力，對實體狀態的預測精度保持了較為穩定的態勢。而CSS對實體狀態的估計存在較大的隨機誤差，因而，CSS機制的通信開銷隨運行時間的延長表現出較大幅度的波動。并且，ESMP較CSS在通信開銷方面平均降低了約36.2%，在通信開銷性能方面ESMP相比CSS有較大幅度的性能增益。

圖3 單周期內不同查詢次數下的預測精度對比

圖4 單周期內不同查詢次數下的通信開銷對比

圖5運行時間的通信開銷對比

6 總結

本文提出了適用于物聯網內容搜索的實體狀態匹配估計方法，設計了等時距與周期內實體狀態估計方法對未來實體狀態進行估計，并依據預測所得實體狀態提出實體有序驗證方法，驗證選定實體與用戶搜索需求的符合狀態，以提高物聯網內容搜索的效率。仿真結果表明，相比現有的典型方法，本文所提實體狀態預測方法具有較高的預測精度，基于所提匹配預測方法的搜索機制具有較低的通信開銷。

［1］ 于海寧， 余翔湛. 物聯網中基于編碼的多路徑并發實體通用搜索算法［J］. 智能計算機與應用， 2013， 3（2）: 25-31. Yu Hai-ning and Yu Xiang-zhan. A multi-path concurrency object universal search （MCOUS） algorithms based on code in internet of things［J］. Intelligent Computerand Applications，2013， 3（2）: 25-31.

［2］ 茹立云， 李智超， 馬少平. 搜索引擎索引網頁集合選取方法研究［J］. 計算機研究與發展， 2014， 51（10）: 2239-2247. Ru Li-yun， Li Zhi-chao， and Ma Shao-ping. Indexing page collection selection method for search engine［J］. Journal of Computer Research and Development， 2014， 51（10）: 2239-2247.

［3］ 李養群， 沈蘇彬， 許斌. 物品萬維網技術綜述［J］.南京郵電大學學報（自然科學版）， 2014， 34（2）: 32-42. Li Yang-qun， Shen Su-bin， and Xu Bin. Technology of web of things: asurvey［J］. Journal of Nanjing University of Posts and Telecommunications （Natural Science）， 2014， 34（2）: 32-42.

［4］ 于海寧， 張宏莉， 方濱興， 等. 物聯網中物理實體搜索服務的研究［J］. 電信科學， 2012， 28（10）: 111-119. Yu Hai-ning， Zhang Hong-li， Fang Bin-xing， et al.. Research on search service for physical entities in the internet of things［J］. Telecommunications Science， 2012， 28（10）: 111-119.

［5］ Benedikt O， Kay R， Friedemann M， et al.. A real-time search engine for the web of things［C］. Internet of Things， Tokyo，2010: 1-8.

［6］ Cuong T and Kay R. Content-based sensor search for the web of things［C］. Global Communications Conference， Atlanta，2013: 2654-2660.

［7］ 唐舟進， 彭濤， 王文博. 一種基于相關分析的局域最小二乘支持向量機小尺度網絡流量預測算法［J］. 物理學報， 2014，63（13）: 57-66. Tang Zhou-jin， Peng Tao， and Wang Wen-bo. A local least square support vector machine prediction algorithm of small scale network traffic based on correlation analysis［J］. Acta Physica Sinica， 2014， 63（13）: 57-66.

［8］ 李增科， 高井祥， 王堅， 等. 利用牛頓插值的GPS/INS組合導航慣性動力學模型［J］. 武漢大學學報（信息科學版）， 2014，39（5）: 591-595. Li Zeng-ke， Gao Jing-xiang， Wang Jian， et al.. Inerialdynamic model of GPS/INS integrated navigation based on newton interpolaion［J］. Geomatics and Information Science of Wuhan University， 2014， 39（5）: 591-595.

［9］ http://db.csail.mit.edu/labdata/labdata.html［OL］. 2014.10.

［10］ 尚軍亮， 方敏. 一種優化的高精度灰色 GM（1，1）預測模型［J］.電子與信息學報， 2010， 32（6）: 1301-1305. Shang Jun-liang and Fang Min. New optimized method of high-precision grey GM（1，1） forecasting model［J］. Journal of Electronics & Information Technology， 2010， 32（6）: 1301-1305.

張普寧： 男，1988年生，博士生，研究方向為物聯網搜索、無線傳感器網絡.

劉元安： 男，1963年生，教授，研究方向為電磁兼容、泛在無線網絡.

吳 帆： 女，1981年生，副教授，研究方向為物聯網搜索、泛在無線網絡.

An Entity State Matching Prediction Method for Content-based Search in the Internet of Things

Zhang Pu-ning Liu Yuan-an Wu Fan Tang Bi-hua Wu Chao
（Institute of Smart Wireless Mobile Information Technology， Beijing University of Posts and Telecommunications， Beijing 100876， China）

Matching prediction with high accuracy of entity state can cansignificantly improve the efficiency of content-based search in the Internet of Things and reduce communication overhead while searching. The equal-interval and during the period entity state prediction methods are proposed， which are applied to the estimation of the entity state at the moment of querying. Moreover， the ordered verification approach is designed to verify the entities in sequence based on the degree of compliance with the searching content， for the sake of enhancing the reliability of searching results. Numerical results show that the proposed entity state prediction approachescan achieve high accuracy， which combines with the ordered verification approach to dramatically improve the performance of communication overheadduring the searching process.

Internet of Things； Content-based search； State prediction； Matching verification

s: The National Natural Science Foundation of China （61170275）； The National 863 Program of China； Civil Space “12th Five-year” Plan Pre-Research Project of Science and Technology； Beijing Higher Education Young Elite Teacher Project； Beijing Key Laboratory of Work Safety Intelligent Monitoring

TP393

A

1009-5896（2015）12-2815-06

10.11999/JEIT150191

2015-02-02；改回日期：2015-08-19；網絡出版：2015-11-01

*通信作者：張普寧 zhangpuningpaper@gmail.com

國家自然科學基金（61170275），國家 863計劃項目，民用航天十二五預研科技項目，北京市高等學校青年英才計劃項目和安全生產智能監控北京市重點實驗室基金