李　勐,王曉峰,崔　莉

(1.中國科學(xué)院計算技術(shù)研究所,北京100190;2.中國科學(xué)院大學(xué),北京100049)

?

一種物聯(lián)網(wǎng)設(shè)備自動描述方法

李勐1,2,王曉峰1,崔莉1

(1.中國科學(xué)院計算技術(shù)研究所,北京100190;2.中國科學(xué)院大學(xué),北京100049)

物聯(lián)網(wǎng)感知設(shè)備的服務(wù)描述文件為海量資源的發(fā)現(xiàn)與檢索提供了有效的支持,是面向服務(wù)的物聯(lián)網(wǎng)架構(gòu)的基礎(chǔ).當(dāng)前服務(wù)描述文件主要通過開發(fā)人員手工撰寫完成,工作量大.現(xiàn)有研究SPITFIRE提出了一種半自動方法協(xié)助開發(fā)人員撰寫服務(wù)描述文件,但方法本身為集中式方法,配置較復(fù)雜且精度過度依賴人工參數(shù)調(diào)優(yōu),不適合大規(guī)模部署.針對物聯(lián)網(wǎng)海量設(shè)備的描述問題,本文提出了一種基于度量學(xué)習(xí)的分布式的物聯(lián)網(wǎng)感知設(shè)備自動描述方法.該方法使用設(shè)備的多種數(shù)值特征作為輸入,利用一種分布式的DBSCAN聚類算法對設(shè)備進行歸類與推導(dǎo),設(shè)備通過歸類結(jié)果可自動生成自身描述文件.該方法利用度量學(xué)習(xí)優(yōu)化聚類的度量函數(shù)以保障精度,以分布式方式進行靈活快速的配置,可減少人工干擾.仿真實驗表明,與使用單一屬性作為度量方式的SPITFIRE相比較,本文方法在獲得對設(shè)備聚類相當(dāng)?shù)牟槿实耐瑫r,查準(zhǔn)率提高了20.4%,更適合于物聯(lián)網(wǎng)海量設(shè)備使用場景.

物聯(lián)網(wǎng);海量設(shè)備;描述文件;分布式;優(yōu)化;聚類

1　引言

隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展與設(shè)備計算能力的提升,越來越多的感知設(shè)備開始以水平化的方式接入網(wǎng)絡(luò).與傳統(tǒng)傳感網(wǎng)有所區(qū)別,物聯(lián)網(wǎng)常包含海量與異構(gòu)的感知設(shè)備.為了便于管理,現(xiàn)有研究與應(yīng)用開始通過人工定義與撰寫設(shè)備功能描述文件,將感知設(shè)備所提供的功能封裝成為服務(wù).面向服務(wù)的物聯(lián)網(wǎng)架構(gòu)可以有效地對資源進行組織,提高設(shè)備的共享程度,解決不同廠商設(shè)備間的連通性問題,用戶通過服務(wù)搜索的方式,可以快速定位物聯(lián)網(wǎng)中的設(shè)備與資源.由于設(shè)備的海量性,現(xiàn)有手工或半自動服務(wù)描述方式工作量較大,本文針對該問題,提出了一種感知設(shè)備服務(wù)描述文件的自動生成方法.

面向服務(wù)的架構(gòu)包含服務(wù)描述語言、協(xié)議、注冊與管理方法三部分技術(shù).現(xiàn)有用于物聯(lián)網(wǎng)的服務(wù)描述語言繼承了傳統(tǒng)的Web服務(wù)描述方法,其中常用的是WSDL[1]、uPnP XML[2],以及OGC組織下的Sensor ML[3].這三類建模語言分別定義了設(shè)備描述規(guī)范,開發(fā)人員編寫對應(yīng)設(shè)備的描述文件,可以完成對物聯(lián)網(wǎng)設(shè)備的描述.但在物聯(lián)網(wǎng)場景下,這種傳統(tǒng)的人工編寫方式會帶來可操作性問題.當(dāng)前,物聯(lián)網(wǎng)設(shè)備具有異構(gòu)、海量的特點,人工撰寫設(shè)備描述文件會導(dǎo)致較大的工作量,整個過程是繁雜、易錯與低效的;此外不同開發(fā)人員的評價標(biāo)準(zhǔn)不一,最終得到的設(shè)備描述文件的可用性會受影響.文獻[4]提出了半自動的設(shè)備描述框架SPITFIRE,利用感知設(shè)備捕獲的數(shù)據(jù)序列的特征.該方法通過聚類將特征類似的設(shè)備歸為一類,同類設(shè)備給予相同的設(shè)備描述標(biāo)簽.這種方式可以有效輔助開發(fā)人員進行設(shè)備描述,但在實現(xiàn)過程中需要人工給定聚類參數(shù);同時,SPITFIRE本身是一種集中式算法,需要輔助的計算設(shè)備,會帶來額外的人工工作量和設(shè)備成本.

理想情況下,設(shè)備的開發(fā)人員無需了解設(shè)備數(shù)據(jù)的具體意義,且無需編寫設(shè)備的服務(wù)描述文件,僅需為設(shè)備添加統(tǒng)一的自動描述程序,設(shè)備的服務(wù)描述文件會隨自動描述程序的執(zhí)行而自動生成.這種設(shè)想在物聯(lián)網(wǎng)感知設(shè)備上具有可行性,原因在于設(shè)備捕獲的諸如溫度、濕度、光照等環(huán)境信號有明顯的數(shù)值特征差異,利用特征的差異與相關(guān)性可能推斷出數(shù)據(jù)屬性甚至地理位置的近似程度.如果能正確獲得不同感知設(shè)備之間的相關(guān)性,則在已知少量設(shè)備描述“標(biāo)簽”的情況下,大量的缺失功能描述文件的設(shè)備可以利用其他有相似數(shù)據(jù)特征的設(shè)備的描述文件進行補全.本文設(shè)想通過物聯(lián)網(wǎng)前端感知設(shè)備的自主協(xié)商,分布式地對感知設(shè)備輸出的數(shù)據(jù)數(shù)值上的相似性進行判斷,利用已有的少量設(shè)備描述信息補全缺失描述,以達到自動撰寫自身的描述文件的目的.

為此,本文在文獻[4]的基礎(chǔ)上,設(shè)計了一種自協(xié)商、易擴展的物聯(lián)網(wǎng)設(shè)備自動描述方法.設(shè)備利用自身與其他設(shè)備采集到的原始數(shù)據(jù)的相關(guān)性,通過分布式地協(xié)商獲得最優(yōu)參數(shù),通過在設(shè)備自身上執(zhí)行聚類,對數(shù)據(jù)本身的意義進行推斷,補全和創(chuàng)建缺失的設(shè)備的文本描述.

本文的主要貢獻有以下兩點:(1)基于度量學(xué)習(xí)思想[5],提出了一種可擴展的設(shè)備相似性度量策略.該策略使用線性規(guī)劃方法,從所有候選度量方式中選擇最優(yōu)組合,線性加權(quán)得到一種區(qū)分能力較強的度量方式,同時推斷出聚類的參數(shù);(2)設(shè)計了一種分布式的、基于DBSCAN[6]的分布式設(shè)備屬性聚類方法,通過此方法,物聯(lián)網(wǎng)感知設(shè)備可以對自身的描述進行推斷.仿真實驗表明,本文的設(shè)備自動描述方法與SPITFIRE方法相比較,在功能描述的查準(zhǔn)率上有明顯優(yōu)勢,在查全率上基本持平.

2　相關(guān)工作

現(xiàn)有的物聯(lián)網(wǎng)服務(wù)描述的研究主要集中于對服務(wù)搜索與設(shè)備發(fā)現(xiàn)功能的支持與設(shè)備服務(wù)運行能耗的控制上.uPnP是最早用于搭建面向服務(wù)的物聯(lián)網(wǎng)的技術(shù)之一,通過重新定義uPnP中的XML來描述物聯(lián)網(wǎng)設(shè)備的靜態(tài)信息,uPnP可應(yīng)用于物聯(lián)網(wǎng)的設(shè)備發(fā)現(xiàn).針對物聯(lián)網(wǎng)設(shè)備資源受限的特點,IrisNet[7]提出了一種整體描述物聯(lián)網(wǎng)子網(wǎng)的方法,考慮到傳感器節(jié)點自身的能量與計算能力,IrisNet將子網(wǎng)的結(jié)構(gòu)、功能特性進行描述之后,存儲于物聯(lián)網(wǎng)網(wǎng)關(guān)上.文獻[8]針對傳感網(wǎng)中Web服務(wù)描述資源占用過多這一現(xiàn)象,提出了一種輕量級的傳感器描述方法.Sensor ML[3]是OGC組織推廣的一種傳感器描述方法以及一套資源定位與搜索工具,最大特點是可以利用語義工具進行設(shè)備地理位置的推理.Sensor ML規(guī)定一套完整的描述規(guī)則和查詢機制,可以對包含Sensor ML描述的物聯(lián)網(wǎng)系統(tǒng)中的設(shè)備與數(shù)據(jù)進行快速查詢.文獻[9]提出了一種語義物聯(lián)網(wǎng)搜索框架,為了獲得更好的搜索效果,研究使用本體對物聯(lián)網(wǎng)進行建模,用戶可使用不同的優(yōu)先級進行定制化搜索.但以上方法均假設(shè)物聯(lián)網(wǎng)開發(fā)人員手工定義設(shè)備描述文件,無法從根本上解決海量感知設(shè)備的描述問題.

物聯(lián)網(wǎng)設(shè)備感知數(shù)值特征的表示方面的研究對于解決設(shè)備自動描述問題也具有借鑒意義.Yan等人[10]提出了一種基于SIFT算法的圖像傳感器的數(shù)據(jù)特征提取的方法,通過對不同圖像特征進行聚類,避免了較大的計算開銷,設(shè)計了一種高效的索引,用于相似圖片的快速查找.Truong等人[11]為了估計傳感器實時數(shù)據(jù)流數(shù)值上的相似程度,提出了一種基于Fuzzy Set的特征提取方法.以上兩種方法可以較好地解決特定領(lǐng)域內(nèi)數(shù)據(jù)特征的提取,從而獲得數(shù)據(jù)之間的相似度,但設(shè)備自動描述任務(wù)面對了更多類型的原始輸入,需要一種擴展性更強的方式.

與本文最為相近的工作是由Kay Romer等人主導(dǎo)的SPITFIRE物聯(lián)網(wǎng)搜索項目[4].該項目完成了一套完整的物聯(lián)網(wǎng)搜索平臺,其中為了防止進行搜索時設(shè)備描述信息過少,引入了一種集中式的半自動的設(shè)備描述框架.SPITFIRE采用一種數(shù)值數(shù)據(jù)與屬性的綁定的方式,通過rdf查詢方法SPARQL,快速定位物聯(lián)網(wǎng)中的資源.由于此項目需要對大量定義用于設(shè)備描述的XML,為了減小工作量,文獻[4]設(shè)計了一種基于數(shù)據(jù)數(shù)值特征聚類的半自動的描述框架.該框架可以為開發(fā)人員提供備選的設(shè)備描述方式,減小了人工撰寫描述文件的工作量.但SPITFIRE存在兩點較為突出的問題:(1)由于基于聚類方法,針對不同類型的感知設(shè)備,開發(fā)人員需對聚類參數(shù)進行調(diào)優(yōu),產(chǎn)生了額外的工作量;(2)該方法是一種集中式算法.在物聯(lián)網(wǎng)的海量設(shè)備場景下通訊開銷較大,同時需要一個計算能力較強的中心設(shè)備進行聚類計算,增加了設(shè)備成本.本文在SPITFIRE搜索框架的基礎(chǔ)上,針對以上兩個問題,設(shè)計了一種全新的分布式設(shè)備自動描述方案.

3　自動描述方法流程

前端感知設(shè)備捕獲到的數(shù)據(jù)序列本身包含大量的特征信息.以室內(nèi)環(huán)境監(jiān)測傳感器為例,環(huán)境監(jiān)測傳感器采集溫度、濕度、光照三類環(huán)境數(shù)據(jù),這三類數(shù)據(jù)在數(shù)值特征上有明顯的差異.圖1顯示了Intel Lab數(shù)據(jù)集[12]一個時間片段內(nèi)不同類型數(shù)據(jù)的數(shù)值分布規(guī)律.其中,室內(nèi)溫度的絕大多數(shù)采樣在18攝氏度到20攝氏度之間波動,濕度和光照均可能在0到最大量程之間波動.由于遮擋、燈光變化等擾動或突發(fā)事件,光照傳感器可能捕獲到較前兩者變化頻率更高的數(shù)據(jù)序列.如果能找到合適的區(qū)分標(biāo)準(zhǔn),則可以區(qū)分不同類別的數(shù)據(jù)序列,為鑒別數(shù)據(jù)的屬性提供依據(jù).

本文建立在以下假設(shè)上:(1)設(shè)備描述只考慮數(shù)據(jù)采集功能,對于非數(shù)據(jù)采集功能,是否可以使用自動描述取決于是否存在一種有效的訓(xùn)練標(biāo)簽獲取方式,本文暫不討論;(2)每個設(shè)備只提供一種數(shù)據(jù)的輸出,每種數(shù)據(jù)輸出對應(yīng)一個實時的數(shù)據(jù)序列,該序列是用于決策的最小單元;(3)設(shè)備兩兩之間均連通,不考慮由于設(shè)備之間的連通性導(dǎo)致的問題;(4)設(shè)備在進行自動描述過程期間沒有休眠.

感知設(shè)備的自動描述可以形式化為一個半監(jiān)督的機器學(xué)習(xí)問題.原始設(shè)備包括少量含有描述信息的設(shè)備與大量不含描述信息的設(shè)備.設(shè)備的描述信息可以看為設(shè)備訓(xùn)練標(biāo)簽,每個感知設(shè)備的采樣信息為一個數(shù)據(jù)樣點.規(guī)定原始狀態(tài)下包含標(biāo)簽的設(shè)備對應(yīng)的采樣信息為訓(xùn)練數(shù)據(jù)樣點,不包含標(biāo)簽的采樣信息為測試數(shù)據(jù)樣點.

本文的自動描述方法分兩個步驟,首先利用已有描述信息的設(shè)備數(shù)值特征,對數(shù)據(jù)整體的參數(shù)特征進行估計.之后,通過原始數(shù)據(jù)的數(shù)值特征對不同設(shè)備進行區(qū)分,根據(jù)區(qū)分情況與同類設(shè)備已有的描述信息,對無描述信息的設(shè)備添加描述,完成設(shè)備自動描述.

圖2展示了自動描述方法的整體過程:(1)開發(fā)人員給定采樣時長,提供候選的特征提取方式,此外如果原始設(shè)備均不包含描述信息,則需要人工給定少量描述信息作為推斷依據(jù);(2)感知設(shè)備啟動之后,統(tǒng)一進行指定長度時間的數(shù)據(jù)采集,并分別將數(shù)據(jù)序列使用(1)中規(guī)定的特征提取方式進行提取;(3)包含標(biāo)簽的設(shè)備進行協(xié)商,確定最優(yōu)度量,同時確定聚類參數(shù);(4)所有設(shè)備進行協(xié)商,在最優(yōu)度量下,使用分布式DBSCAN方法,對設(shè)備進行聚類;(5)依據(jù)類中的已有標(biāo)簽,為同一類設(shè)備給定標(biāo)簽.

本文采用了一種簡化的度量學(xué)習(xí)策略,這種度量學(xué)習(xí)策略主要用于優(yōu)化原始數(shù)據(jù)特征之間的距離函數(shù);同時,該優(yōu)化過程中獲得了設(shè)備數(shù)據(jù)特征的整體分布情況,可以用以獲得后半部分的推斷方法的輸入?yún)?shù).

在進行設(shè)備間關(guān)系推斷時,使用DBSCAN聚類方法作為基礎(chǔ)方法主要是出于以下考慮.首先,感知設(shè)備自動描述任務(wù)可以使用分類方法或聚類方法實現(xiàn),但分類方法可能會遺漏部分類.具體而言,如果訓(xùn)練集本身不包含某類數(shù)據(jù)點,該類數(shù)據(jù)樣點無法參與訓(xùn)練過程,所獲得的分類器無法區(qū)分該類數(shù)據(jù).在海量設(shè)備的場景下,訓(xùn)練集樣點的數(shù)目將遠小于測試集,這種情況將大大影響算法的準(zhǔn)確率.其次,其相對于其他聚類方法,DBSCAN本身特性決定可以更好地被改寫為分布式的方法.DBSCAN在執(zhí)行過程中每個節(jié)點不需要實時了解全局信息,同時節(jié)點自身狀態(tài)較為簡單.已知聚類參數(shù)的情況下,單個設(shè)備僅需知道與其他設(shè)備之間的特征距離,判定自身是否屬于核心點.此外,在節(jié)點數(shù)目較多的情況,這種方法下具有較小的計算量,整體迭代次數(shù)易于估計.

4　自動描述方法的實現(xiàn)

本節(jié)對分布式度量優(yōu)化方法和分布式聚類方法兩個關(guān)鍵步驟進行描述.為方便表述,下文定義參與自動描述的感知設(shè)備數(shù)目為N,N中包括已包含描述信息的設(shè)備NL數(shù)目,其中NL?N.每個設(shè)備產(chǎn)生的數(shù)據(jù)序列有M種候選特征可以選擇,使用不同的特征參與相似度計算會得到不同的結(jié)果.設(shè)備xi與xj之間的、度量f下的距離記為f(xi,xj).

4.1分布式度量優(yōu)化方法

度量優(yōu)化的目的是根據(jù)少量的已有標(biāo)簽設(shè)備的數(shù)值特征,獲得一個具有較好特性的相似性度量方式.本小節(jié)首先將用于設(shè)備描述的度量優(yōu)化問題建模成為一個線性規(guī)劃問題,之后利用線性規(guī)劃可行域為凸集這一特性,設(shè)計一種基于迭代的分布式優(yōu)化方法,可計算指定精度的數(shù)值解.

物聯(lián)網(wǎng)感知設(shè)備的原始數(shù)據(jù)較為多樣,但仍可以根據(jù)其數(shù)值分布情況、頻域、變化速率等數(shù)值特征進行區(qū)分.可以使用的特征包括不同窗口大小下的直方圖、某個頻段的FFT系數(shù)、小波系數(shù)等.但不同的特征組合對數(shù)據(jù)的區(qū)分能力不盡相同,一般情況下需要人工對數(shù)據(jù)集的物理含義進行研究,以確定使用一個或一組特征作為度量,否則,需要學(xué)習(xí)算法本身對數(shù)據(jù)集的特性進行分析.本文考慮使用一種自動的方式對度量進行優(yōu)化.人工選擇多組度量作為候選后,算法可以從這些度量中找到若干最為有效的度量.

現(xiàn)有研究中,度量學(xué)習(xí)(Metriclearning)[5,13]提供了一類針對度量函數(shù)的優(yōu)化方法.度量學(xué)習(xí)通常指定一個優(yōu)化目標(biāo),根據(jù)已有分類標(biāo)簽優(yōu)化距離的相關(guān)度矩陣,通過對度量的優(yōu)化,使節(jié)點變得更容易區(qū)分.但度量學(xué)習(xí)需要計算一個完整的相關(guān)性矩陣,在分布式感知設(shè)備的環(huán)境下,設(shè)備需要多次通訊與迭代才能完成.為了避免過大的計算量,本文使用了一種簡化的度量學(xué)習(xí)方法,僅計算對角線上的元素權(quán)重以替代相關(guān)性矩陣.以下給出具體計算方法.

首先定義距離函數(shù).M種不同的度量記為fk,每種度量對應(yīng)權(quán)重參數(shù)λk,定義兩個感知設(shè)備xi與xj之間的距離F:

(1)

其次,需選取合適的優(yōu)化目標(biāo).本文選擇不同類之間“最小距離最大化”作為優(yōu)化準(zhǔn)則.這種選擇目的在于可以較好地配合DBSCAN聚類算法:(1)這種方式可以最大程度地避免誤判,將不同類別的設(shè)備錯歸為一類.DBSCAN的同類判定依據(jù)是數(shù)據(jù)點之間雙向密度連通,根據(jù)最小距離最大化設(shè)定DBSCAN核心點判定半徑,可以避免不同類之間最近兩點直接密度相連.如果兩類之間的間隙不出現(xiàn)測試點,理論上可以保證不出現(xiàn)錯判,文本在4.2節(jié)參數(shù)推斷部分給出了詳細說明；(2)這種方式便于計算.不同于度量學(xué)習(xí)中常用的類內(nèi)距離和最小化等方法,最小距離最大化可以方便地轉(zhuǎn)化為線性規(guī)劃問題,可以進行快速的求解,且可以方便地改寫為分布式方法.原問題可以表示為:

(2)

(3)

在優(yōu)化進行之前,假設(shè)每個設(shè)備已知不同度量下自身與其他所有設(shè)備的距離,同時存儲一個初始參數(shù)向量λ與優(yōu)化目標(biāo)v.在每次迭代完成之后,設(shè)備均可以通過廣播,同步當(dāng)前時刻的解向量(λ1,…,λM,v).迭代的步長記為Δ,有標(biāo)簽感知設(shè)備數(shù)據(jù)序列之間的度量記為d,整個迭代過程分三個主要步驟:

(2)“瓶頸節(jié)點”x0嘗試對自身的解向量λ進行優(yōu)化,得到λ′.由于存在等式約束,使用類似SVM中的SMO技術(shù)[15],同時嘗試以步長Δ調(diào)大一個值λi并調(diào)小另一個值λj,原有的參數(shù)向量會被改寫為(λ1,…,λi+Δ,…,λj-Δ,…,λM).如果已經(jīng)嘗試過所有組合,則已經(jīng)獲得了最優(yōu)的解向量,迭代結(jié)束;否則進入步驟3.

(3)“瓶頸節(jié)點”x0廣播調(diào)整后的λ′,通知其他設(shè)備對λ′進行測試.其他設(shè)備獲得新的參數(shù)后,重新計算自身的最小距離dy,之后全局再次執(zhí)行步驟1中的最短距離搜索過程,發(fā)起設(shè)備x0可以獲得一個新的距離,如果新的距離大于原有距離,說明步驟2的優(yōu)化是有效的,本輪迭代結(jié)束,回到步驟1.如果新的距離小于原有距離,說明2中嘗試的優(yōu)化無效,回退到步驟2重新選擇.

該分布式算法是一致的,即所有設(shè)備均具有相同的執(zhí)行邏輯.節(jié)點i使用xi表示;其中xi.s表示節(jié)點當(dāng)前狀態(tài),包括“瓶頸節(jié)點”狀態(tài)和正常節(jié)點狀態(tài);v表示當(dāng)前的目標(biāo)函數(shù)值,λ表示節(jié)點當(dāng)前的參數(shù)值.算法輸入為每次迭代的步長Δ,算法的輸出為迭代最終的目標(biāo)函數(shù)值vopt以及參數(shù)值λopt.整體過程可由算法1表示.

4.2分布式聚類方法

如算法2所示，分布式聚類方法利用上節(jié)求得的最優(yōu)度量,可以快速計算所有設(shè)備(有標(biāo)簽設(shè)備與無標(biāo)簽設(shè)備)的歸屬信息.相較于集中式方法,分布式DBSCAN可以充分利用設(shè)備的并行特性,使用一種異步非阻塞方式完成聚類.每個節(jié)點首先通過鄰域內(nèi)節(jié)點的密度,判定自身是否是核心節(jié)點,之后核心節(jié)點自發(fā)地掃描鄰域內(nèi)的節(jié)點,如果這類節(jié)點與自身距離足夠接近,則可以判定自身與鄰居節(jié)點是否屬于同一類,并給定相同的類標(biāo)簽,這里的距離是指4.1中得到的度量上的距離.本小節(jié)主要討論分布式DBSCAN方法的設(shè)計以及參數(shù)的選取.

設(shè)候選特征數(shù)目為M,設(shè)備節(jié)點數(shù)目為N,任意兩設(shè)備間最長通訊時間為tm.聚類參數(shù)包括核心點判定半徑為與核心點密度閾值為N.參數(shù)M已知,N與tm可通過全網(wǎng)廣播獲得,與N的選擇方法將在本小節(jié)后半段給出.聚類具體步驟如下:

(1)設(shè)備初始化.所有設(shè)備x在啟動后,使用唯一的序號作為初始的類標(biāo)簽,該標(biāo)簽可以使用設(shè)備的IP地址等固有信息生成.同時,計算一段時間內(nèi)的數(shù)據(jù)序列的M種特征并進行廣播,收取其他設(shè)備x′廣播的特征.

(2)設(shè)備對自身是否是核心點進行判斷.每個設(shè)備x使用4.1中得到的距離函數(shù)F(x,x′|λ)對距離進行計算,獲得距離小于的鄰域內(nèi)的節(jié)點N(x).如果節(jié)點個數(shù)|N(x)|>N則標(biāo)記自身為核心點,否則自身停止操作,等待其他設(shè)備的通知信息.

(3)設(shè)備自發(fā)擴散自身類標(biāo)簽.每個核心點設(shè)備x對相鄰節(jié)點N(x)進行掃描,驗證每個節(jié)點x′是否是核心點,如果是核心點則協(xié)商兩者公用的類標(biāo)簽號,這里始終選擇字典序較小的標(biāo)簽號作為兩者的公用標(biāo)簽.每個核心節(jié)點對于所有相鄰節(jié)點的掃描完成之后進入等待狀態(tài).

(4)設(shè)備對結(jié)束時機進行判定.任何等待時間超過N tm的節(jié)點均認為自身已經(jīng)獲得了正確的類標(biāo)簽.

步驟4的判定依據(jù)如下.由于節(jié)點的標(biāo)簽可能被多次改寫,所以節(jié)點僅根據(jù)自身的分類信息并不能判定算法的結(jié)束.本文采用的方案是為每個節(jié)點設(shè)置一個超時時間N tm.原因在于,最壞情況下,網(wǎng)絡(luò)所有測試點均密度連通,執(zhí)行步驟2、3進行擴散時,每次只能加入一個測試點,此時需要N個周期的時間才能嚴(yán)格判定聚類過程的結(jié)束.

DBSCAN所需要確定核心點半徑參數(shù)和密度閾值參數(shù)N,而這兩種閾值可以使用4.1中的優(yōu)化結(jié)果進行推斷.在設(shè)備描述場景下誤判會造成嚴(yán)重的后果,所以在參數(shù)選擇方式上,盡可能使用保守的策略,以減少誤判.本文利用4.1節(jié)中的距離優(yōu)化的目標(biāo)函數(shù)值v作為以上兩個參數(shù)選擇的依據(jù).v的實際意義是兩個不同類別的聚簇之間的間隙,距離大于v的聚簇將無法進行合并.但由于v本身是使用有標(biāo)簽集合計算得到的,而該數(shù)據(jù)集只是全部數(shù)據(jù)的一個子集,所以在全部設(shè)備數(shù)據(jù)集上運行時,v產(chǎn)生的間隙很有可能無法將兩個類區(qū)分.

方法中的密度閾值選擇N=N(2)M.確定半徑參數(shù)后,在理想情況下,如果類的中間區(qū)域沒有數(shù)據(jù)樣點,則選擇一個盡可能小的N即可.但在實際情況中,由于有標(biāo)簽設(shè)備個數(shù)NL遠小于全部設(shè)備個數(shù)N,4.1節(jié)得到的間隙v中很有可能存在大量數(shù)據(jù)點,這樣以來使用一個較小的N可能會導(dǎo)致錯誤的類合并.當(dāng)所有的測試點在特征空間均勻分布時,N參數(shù)選擇最有可能導(dǎo)致錯誤的合并.在數(shù)據(jù)樣點均勻分布的情況下,可以估計出聚簇間隙中的數(shù)據(jù)點的上限,以此推斷N的取值下界.令全部數(shù)據(jù)的寬度為1,全部測試點的數(shù)目為N,那么每個間隙的寬度為v,間隙中的數(shù)據(jù)樣點出現(xiàn)的概率為sM/1,s為數(shù)據(jù)樣點可能出現(xiàn)的區(qū)域,故間隙中樣點出現(xiàn)次數(shù)的期望為NsM.由于之前已經(jīng)獲得了半徑閾值,可以將空間大小近似估計為s=(2)M,所以本文選擇N(2)M作為密度閾值.圖3顯示了在IntelLab數(shù)據(jù)集上使用不同參數(shù)能達到的最佳的F-measure值,圖中標(biāo)注的點為使用以上參數(shù)得到的F-measure值.以上方法較為保守地進行了參數(shù)選擇,且獲得了較好的F-measure值.

定義fopt(xi,xj)為由4.1中的算法求得的最佳距離函數(shù),x.L為x的聚類標(biāo)簽,分布式聚類過程如算法2所示.該分布式聚類算法的最壞時間復(fù)雜度等價于上文所討論的超時時間,為O(N tm).平均情況下,設(shè)原始設(shè)備最終可被歸為K類,那么整體的時間消耗等價于所有類內(nèi)部遍歷過程的最大時間消耗,均攤時間復(fù)雜度可以估計為O(tmlogN/K).

5　仿真實驗

實驗包含兩部分,首先對參數(shù)選擇方法的有效性進行評估,之后評估算法整體性能,重點測試算法的準(zhǔn)確性.本實驗需要使用較多的節(jié)點設(shè)備,故采用了仿真實驗的方式進行驗證.仿真采用以下方式進行:每次循環(huán)分別處理每個節(jié)點的消息和事件,之后將狀態(tài)進行存儲,以模擬節(jié)點狀態(tài)的變化;每次循環(huán)使用隨機的順序執(zhí)行不通過節(jié)點的程序片段,以模擬真實情況的并發(fā)特性.

實驗使用了IntelLab數(shù)據(jù)集作為驗證,使用Matlab進行仿真.IntelLab數(shù)據(jù)集包含54個節(jié)點,每條數(shù)據(jù)包含溫度、濕度、光照、節(jié)點電壓4類數(shù)據(jù).本實驗選擇上述4類數(shù)據(jù),同時選擇了20個節(jié)點,截取了其中的一個小時的數(shù)據(jù)作為原始采樣.當(dāng)使用全部數(shù)據(jù)輸?shù)奖疚牡姆椒〞r,整個輸入規(guī)模為80條原始數(shù)據(jù),最終聚為4類.

實驗驗證聚類結(jié)果準(zhǔn)確率時,使用F-measure[16]作為衡量指標(biāo).F-measure方法可以綜合聚類方法的查準(zhǔn)率與查全率性能,其表達式為:

F=(1+β2)PR/(β2P+R)

(4)

其中β為查準(zhǔn)率與查全率的權(quán)重參數(shù),實驗中使用β=1.對于聚類操作,查準(zhǔn)率為正確分入該類的數(shù)據(jù)點數(shù)目與全部分入該類的數(shù)據(jù)點數(shù)目的比例,P是每個類查準(zhǔn)率的平均值;查全率為正確分入的數(shù)據(jù)點數(shù)目與應(yīng)該分入該類的數(shù)據(jù)點數(shù)目的比例,R為每個類查全率的平均值.實驗使用F、P、R這三項指標(biāo)評價方法的準(zhǔn)確率.

5.1參數(shù)選擇方法效果評估

本小節(jié)對4.2節(jié)所使用的參數(shù)選擇方法的效果進行了評估.實驗分別測試了個數(shù)閾值參數(shù)N與核心點判定半徑閾值取不同值時(本文針對IntelLab數(shù)據(jù)集,取參數(shù)∈[1,5],搜索步長為1,取參數(shù)N∈[0.02,0.2],搜索步長為0.02),使用分布式聚類算法得到可以得到在不同網(wǎng)絡(luò)規(guī)模下的查準(zhǔn)率與查全率兩種指標(biāo)的最優(yōu)值的與平均值,以對比4.2節(jié)的方法的效果.距離函數(shù)均使用已進行優(yōu)化的函數(shù).

實驗結(jié)果由圖4所示.其中星標(biāo)線條為聚類方法的查準(zhǔn)率,正方形標(biāo)記為聚類方法的查全率;對于每組數(shù)據(jù),點狀虛線標(biāo)記的數(shù)據(jù)為使用4.2節(jié)方法推測獲得的參數(shù)的聚類效果,其他兩條數(shù)據(jù)分別為最佳參數(shù)條件下的結(jié)果與平均情況.可以看出,本文的參數(shù)獲取方法在查準(zhǔn)率上有較為明顯的優(yōu)勢,在查全率上并沒有很好的逼近使用最佳參數(shù)的查全率.但由于平均情況的高查全率建立在較高的錯判可能性上,并不宜于在設(shè)備描述場景下使用;相較而言,通過優(yōu)化方法推斷得到的參數(shù)具有較高的查準(zhǔn)率,更為適合設(shè)備描述場景.

5.2整體準(zhǔn)確率評估

本文采用以下方式進行整體性能評估實驗:分別選擇4、8、12、16、20個原始設(shè)備的4類數(shù)據(jù)作為輸入,進行5次實驗.每次實驗選用1/4的數(shù)據(jù)作為度量優(yōu)化數(shù)據(jù),選用全部數(shù)據(jù)作為分布式聚類數(shù)據(jù).實驗主要用于對比基于分布式度量優(yōu)化方法的特點,使用SPITFIRE中的設(shè)備描述方法作為參照.實現(xiàn)本文度量選擇方法時,實驗選用了EMD、FFT、DIFF三種度量方式.EMD(EarthMover′sDistance)可以較好地衡量原始數(shù)據(jù)直方圖之間的相似程度;FFT反映出數(shù)據(jù)頻域內(nèi)的特性;DIFF計算兩個近鄰數(shù)據(jù)之間的差值,并對差值進行了直方圖統(tǒng)計,計算直方圖之間的近似程度.SPITFIRE的實現(xiàn)方法較為簡單,僅選用單個特征作為距離函數(shù)對SPITFIRE進行模擬.實驗中確定聚類參數(shù)時,為了確保公平,均使用了度量優(yōu)化產(chǎn)生的自動參數(shù).

圖5顯示了不同輸入規(guī)模下不同方法的查準(zhǔn)率P,其中Distributed-opt是度量經(jīng)過優(yōu)化后最終聚類的準(zhǔn)確結(jié)果.結(jié)果表明,使用了分布式度量優(yōu)化的方法在不同網(wǎng)絡(luò)規(guī)模下的查準(zhǔn)率均優(yōu)于使用單一度量的方法.這主要得利于4.2中較為保守的參數(shù)選擇策略.在IntelLab數(shù)據(jù)集下,這種方式可以達到93%的準(zhǔn)確率,比平均的單一的特征選擇的準(zhǔn)確率高出20.4%,比最壞情況平均高出31.1%.實驗表明包含分布式度量優(yōu)化的分布式聚類具有較高的查準(zhǔn)率.

類似的,圖6顯示了不同輸入規(guī)模下算法的查全率R.圖中的查全率相對于其他方法沒有顯著的提高,在IntelLab數(shù)據(jù)集上多次運行發(fā)現(xiàn)查全率相對于平均水平僅提高了2%,沒有明顯變化.這種結(jié)果的原因有2:(1)4.1中提出的優(yōu)化方法對于離群點過于敏感;(2)真實數(shù)據(jù)集在不同度量下并不規(guī)則.以上兩點導(dǎo)致度量優(yōu)化本身對相同類內(nèi)部節(jié)點的連通性造成了影響.可能的解決方案是在4.1的優(yōu)化目標(biāo)上加入松弛變量作為權(quán)衡.

圖7顯示了不同方法的查準(zhǔn)率、查全率,以及在β=1時的F-measure值的綜合對比.其中LP-opt是本文基于線性規(guī)劃完成的一個集中式方法,準(zhǔn)確性略好于分布式方法Distributed-opt,原因在于分布式方法進行迭代求解時引入的誤差.總體上,本文的兩種基于優(yōu)化的方式在查準(zhǔn)率P相對于使用單一特征作為度量的SPITFIRE方法具有明顯優(yōu)勢,在查全率上與基本持平.

6　結(jié)束語

本文討論了海量設(shè)備場景下,編寫物聯(lián)網(wǎng)設(shè)備描述文件所面對的問題與挑戰(zhàn),提出了一種用于物聯(lián)網(wǎng)感知設(shè)備的自動描述方法.方法利用不同感知設(shè)備采集到的數(shù)據(jù)數(shù)值特性之間關(guān)系,通過設(shè)備之間的協(xié)商,自動獲得自身的描述.相對于現(xiàn)有的其他方法,本文提出的方法具有兩個明顯優(yōu)勢.首先,本方法是一種分布式的方法,更有利于設(shè)備的快速部署;其次,本方法可以實現(xiàn)“零輸入”,依靠現(xiàn)有的少量描述信息即可進行推斷,可以達到較高的準(zhǔn)確率.

一個準(zhǔn)確完整的物聯(lián)網(wǎng)設(shè)備描述文件對于物聯(lián)網(wǎng)設(shè)備與資源的發(fā)現(xiàn)與共享具有重要意義.本文提出的方法在查全率與方法魯棒性上仍有進一步的改進空間;此外本方法只能應(yīng)用于感知設(shè)備,對于更為復(fù)雜的中間設(shè)備的自動描述任務(wù),需要功能更強的推理機制去完成,這均將是未來的工作方向.

[1]Web Services Description Language (WSDL) 1.1[EB/OL].http:// www.w3.org/TR/wsdl.2001-3-15.

[2]Universal Plug and Play (uPnP)[EB/OL].http://www.upnp.org.2014-4-20.

[3]Sensor Model Language (SensorML)[EB/OL].http://www.opengeospatial.org/standards/sensorml.2014-2-24.

[4]Dennis Pfisterer,et al.SPITFIRE:toward a semantic web of things[J].Communications Magazine,2011,49(11):40-48.

[5]Eric P,et al.Distance metric learning with application to clustering with side-information[A].Advances in neural information processing systems[C].USA:AAAI Press.2002.521-528.

[6]Ester M,et al.A density-based algorithm for discovering clusters in large spatial databases with noise[A].KDD 96[C].New York:ACM Press.1996.226-231.

[7]Phillip B,Gibbons,et al.Irisnet:An architecture for a worldwide sensor web[A].Pervasive Computing[C].USA:IEEE Press.2003.22-33.

[8]Nissanka B P,et al.Tiny web services:design and implementation of interoperable and evolvable sensor networks[A].Proceedings of the 6th ACM conference on Embedded network sensor systems[C].New York:ACM.2008.31-36.

[9]Charith P,et al.Context-aware sensor search,selection and ranking model for internet of things middleware[A].IEEE 14th International Conference on Mobile Data Management[C].USA:IEEE Press.2013.314-322.

[10]YAN Tingxin,et al.Distributed image search in camera sensor networks[A].Proceedings of the 6th ACM conference on Embedded network sensor systems[C].New York:ACM Press.2008.155-168.

[11]Cuong Truong,et al.Fuzzy-based sensor search in the web of things[A].Internet of Things (IOT),2012 3rd International Conference on the[C].USA:IEEE Press.2012.127-134.

[12]Intel Lab Data,[EB/OL].http://db.csail.mit.edu/labdata /labdata.html.2004-6-2.

[13]Brian Kulis.Metric learning:A survey[J].Foundations & Trends in Machine Learning,2012,5(4):287-364.

[14]Boyd,S,Vandenberghe,L.Convex Optimization[M].Cambridge:Cambridge University Press,2004.146-152.

[15]Platt,J(1998).Sequential minimal optimization:A fast algorithm for training support vector machines[R].http:// www.msr-waypoint.com/pubs/69644/tr-98-14.pdf.1-21.

[16]David MW Powers.Evaluation:from precision,recall and F-measure to ROC,informedness,markedness & correlation[J].Journal of Machine Learning Technologies.2011,2(1):37-63.

李勐男,1989年出生,現(xiàn)為中科院計算技術(shù)研究所博士研究生.主要研究方向為物聯(lián)網(wǎng)資源的發(fā)現(xiàn)與檢索.

E-mail:limeng@ict.ac.cn

王曉峰男,1978年出生,博士,目前為中國科學(xué)院計算技術(shù)研究所助理研究員.主要研究方向為物聯(lián)網(wǎng)大數(shù)據(jù)處理、智能移動計算、數(shù)據(jù)挖掘、人工智能.

E-mail:wangxiaofeng@ict.ac.cn

崔莉(通信作者)女,1962年出生,博士,中國計算機學(xué)會高級會員,中國科學(xué)院計算技術(shù)研究所研究員、博士生導(dǎo)師、從事無線傳感器網(wǎng)絡(luò)相關(guān)研究.

E-mail:lcui@ict.ac.cn

An Automatic Device Describe Method for Internet of Things

LI Meng1,2,WANG Xiao-feng1,CUI LI1

(1.InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100190,China; 2.UniversityofChineseAcademyofSciences,Beijing100049,China)

Service description file,which is fundamental for the service-oriented architecture,can be used by the IoT sensing devices to accelerate resource discovery and searching processes.Currently,these files are mostly written manually by the device developers,this process is inefficient and fallible.The state-of-art method SPITFIRE can generate the devices' description in a semi-automatic way,but its configuration can be trivial and its accuracy still can be improved.In this paper,we proposed a novel automatic device description method,with which devices can automatically generate their individual description.We designed a clustering algorithm based on DBSCAN to infer the description of sensing device,taking advantages of existing descriptions and the data features of series gained by data sampling.A metric learning algorithm is also implemented to optimize the parameter used by the clustering algorithm.All the routines run independently on different devices,and no manual intervention is needed during the self-description process.Through simulation,we show that this method has a prominent advantage of precision over other state-of-art methods,making our method more suitable for the massive IoT devices.

internet of things;massive device;description file;distributed;optimization;clustering

2014-07-22;

2015-07-24;責(zé)任編輯:馬蘭英

中國科學(xué)院戰(zhàn)略性先導(dǎo)科技專項(No.XDA06010403);國家國際科技合作專項(No.2013DFA10690);國家自然科學(xué)基金(No.61202211)

TN911.23

A

0372-2112 (2016)05-1055-09

電子學(xué)報URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.007