物聯網中基于編碼的多路徑并發實體通用搜索算法

摘要：物聯網中許多應用都涉及實體搜索定位。由于物聯網中實體類型、通信協議、隸屬機構、信息存儲組織結構的差異導致了物聯網被割裂為相互獨立，互不協作的子網絡，資源得不到有效利用。基于地標系統的實體搜索定位體系結構是一個開放的、多層多級的、分布式的體系結構，可以有效的整合物聯網中的海量實體的信息和各種實體搜索服務。在此體系結構的基礎上提出的MCOUS算法采用本地搜索與全局搜索并發進行的多路徑搜索策略，高效獲取物聯網中任意類型實體的位置信息。

關鍵詞：物聯網； 層次結構； 實體搜索； 并發搜索

中圖分類號：TP393 文獻標識碼：A文章編號：2095-2163（2013）02-0025-07

0引言

“物聯網”在繼計算機、互聯網之后，形成了世界信息產業的第三次浪潮，由此而引領了國內外學界和工業界的廣泛關注及討論熱潮之所趨[1]。物聯網是通過射頻識別（RFID）、紅外感應器、全球定位系統、激光掃描器、手機、智能終端等信息傳感設備，遵從約定協議完成物與物，物與人，人與人之間的信息交換和通訊，從而實現識別、定位、跟蹤、監控和管理的一種智能化網絡[2-3]。而當物聯網與互聯網相連接時，即構架了一種虛擬網絡和現實世界實時交互的新型系統[4]，實現了無處不在的數據感知。物聯網一方面可以提高經濟效益，大大節約成本；另一方面可以為全球經濟的復蘇提供強大技術動力。目前，美國、歐盟、中國等國均在投入巨資實施開展物聯網的探索研究。

物聯網快速發展的同時，也面臨著許多挑戰[5～7]。其中，如何有效整合物聯網中海量的實體信息，以及如何快速獲取目標實體的位置信息，是迫切需要解決的關鍵現實問題。目前，物聯網實體定位技術主要包括：基于RFID的實體定位技術，基于地球表面的實體定位技術以及基于衛星的實體定位技術。物聯網中實體的定位技術在實體搜索、定位過程中仍然存在著以下問題：

（1）定位技術在定位精度、靈敏度、速度以及可用性方面都存在著明顯的不足，有效工作的范圍有限，對地形環境和信號覆蓋范圍具有較強的依賴性。

（2）物聯網中實體類型互不相同，包括電子標簽、傳感器、手機、車載設備等，同時各類實體的通信技術也彼此各異，例如RFID、WiFi、Zigbee等。上述差異使得目前的定位系統往往只針對同一類實體，缺乏普遍性和通用性。

（3）物聯網中，實體隸屬于不同機構，每個機構部署的實體數量和范圍十分有限，且隸屬于不同機構的實體之間互不通信，各機構之間無法實現信息共享，這就大大降低了實體搜索定位的成功率和準確率。

目前，尚未研發得到一個開放的體系結構和通用的搜索定位算法能夠結合以上的搜索定位技術，并整合各機構的實體信息和相應的信息服務，使各實體高度協調、彼此協作，最大化地利用一切資源，高效獲取目標實體的位置信息。為解決上述問題，本文提出基于地標系統的物聯網實體搜索體系結構，并在其基礎上提出了基于編碼的多路徑并發實體通用搜索算法（簡稱MCOUS算法）對物聯網中的任意實體可以隨時隨地地進行搜索定位。第2期于海寧，等：物聯網中基于編碼的多路徑并發實體通用搜索算法智能計算機與應用第3卷

本文的結構如下：第1節描述基于地標系統的物聯網實體搜索體系結構；第2節在該體系結構的基礎上提出MCOUS算法；第3節對MCOUS算法進行了實驗仿真分析；第4節結論。

1基于地標系統的物聯網實體搜索體系結構

基于地標系統的物聯網實體搜索體系結構是一個分層、分級、開放、分布式的體系結構，全球管理機構可以公開、公平、盡職盡責地履行管理職能，其他機構和個人則可以自愿加入或退出該體系結構。各個機構存儲整理隸屬于該機構的實體信息，也提供相應信息服務（Information Service）。通過體系結構的標準接口，各個機構可隨時隨地將其隸屬實體信息及有關信息服務整合到體系結構中。各個實體也能以個體的形式加入體系結構中，使不同類型、不同隸屬的實體協調合作，共同實現通用實體搜索服務。 基于地標系統的物聯網實體搜索體系結構自下而上分為地標層、終端層和數據服務層三個層次，如圖1所示。下面將分別描述這三個層級的構成及職能。

.1地標層

在地標層中部署了一個全局范圍的電子地標系統，通過電子地標系統可以實現建立“數字城市”乃至“數字地球”的目標。電子地標系統由分布在全局范圍內的電子地標節點及其通信協議構成，電子地標節點存儲其固定位置處的相關信息（例如，經緯度，地域等），而其部署策略則要根據實際地形環境和應用需求切實、合理地進行制定。電子地標節點向其附近實體周期性地廣播包含其位置信息的消息，接收到該消息的實體則根據當前需要對自身的位置信息予以更新，進而實現了實體位置的自感知。在體系結構中，還存有一類特殊實體，本身屬于終端層，但卻可以自發協助地標系統賦予其他終端層實體位置信息，例如裝有GPS設備的智能終端。這類實體可以移動，因而更加靈活。當電子地標節點出現故障或電池耗盡時，該類節點就可以幫助地標系統快速恢復，保障地標系統的可用性和穩定性。

1.2終端層

終端層是物聯網數據感知和信息輸入的部分，終端層的實體采集信息數據，經過簡單的處理上傳給數據服務層。終端層是由大量相互獨立的Ad hoc網絡構成。其中，每個Ad hoc網絡由各種不同類型的、且具備通信能力的實體根據各自的通信范圍自發組成。實體也可以隨時隨地加入或退出終端層。當實體進入物聯網之前，需完成以下兩步工作：

（1）規范實體的編碼，使實體編碼具有全局唯一性，可被物聯網資源尋址系統正確解析，文獻[8]中提出了一種規范不同機構編碼的方法；

（2）在物聯網資源尋址系統中進行注冊，具體地，在體系結構中，實體需要在數據服務層的編碼解析服務系統（CNS，Code Naming Services）中進行注冊，這個注冊過程可以由實體隸屬機構代理完成，也可以由實體獨立完成。同一Ad hoc網絡中的實體通過約定的通信協議實現相互通信和信息共享，不同Ad hoc網絡中的實體則通過數據服務層實現相互通信和信息共享。終端層中的實體可以根據標準接口自主參與消息的轉發和上傳，終端層對用戶的消息請求提供盡力交付的服務。

1.3數據服務層

數據服務層由三部分構成： CNS系統、實體隸屬機構提供的實體搜索服務以及本文提出的實體通用搜索服務。下面介紹數據服務層的這三個組成部分。

1.3.1CNS系統

在物聯網中需要一個資源尋址系統解析實體編碼，該系統應當具有擴展性、靈活性、異構性、兼容遺留系統以及易維護等特性。當應用程序獲取到實體編碼時，有時則需要根據編碼找到該實體的詳細信息和相應信息服務，本文提出的CNS系統即實現了編碼到實體詳細信息和信息服務的尋址過程。CNS系統將每一個實體編碼記錄到一個或多個通用資源標志（URI，Universal Resource Identifier）的映射關系隊列中，這些URI既可以是標識實體信息存儲的數據服務器，也可以是標識實體具有的某種信息服務的接口。CNS系統是一個自動的網絡服務系統，并具有多層多級分布式、易緩存性、冗余性和擴展性等特點。CNS系統中設有一個根服務器，CNS根服務器將實體編碼解析權委派給全球的各個區域，區域級CNS服務器將實體編碼解析權按照行業劃分委托給各個行業級CNS服務器，每個行業級的CNS服務器再進一步將實體編碼解析權委派給各個機構。各機構建立存有尋址信息的本地的CNS服務器，并向上層CNS服務器申請注冊加入CNS的樹形架構，CNS的基礎服務器的樹形架構如圖2所示。當需要進行實體編碼解析服務時，首先在本地CNS服務器中進行解析，如果無法解析，本地CNS服務器將向根CNS服務器發出查詢請求，根CNS服務器根據編碼規則即可確定能夠解析編碼的CNS服務器，本地CNS服務器隨即向該CNS服務器發出查詢請求，該CNS服務器回復解析結果，本地CNS服務器緩存這個解析結果，至此完成實體編碼解析過程。由此過程可知，利用CNS系統可以將不同區域、不同行業、不同機構的實體信息及相關的信息服務有效地組織起來。

1.3.2隸屬機構提供的實體搜索服務

實體隸屬機構提供實體的詳細信息，同時可能為隸屬實體提供搜索服務以響應收到的搜索請求。實體隸屬機構提供實體搜索服務接口的URI，通過URI可以鏈接到實體搜索服務的信息系統，由該信息系統響應處理實體的搜索請求消息，并回復包括目標實體位置信息在內的應答消息。這類實體搜索服務由各個機構根據自身的需求量身定制，在服務適用實體、實現技術、使用權限等方面也各不相同，例如，通信運營商利用基站和GPS為手機用戶提供實體搜索服務，而某超市利用RFID技術為出售商品提供實體搜索服務，這兩種服務就是兩類由不同機構運營實現的完全獨立的搜索服務。

1.3.3實體通用搜索服務

在物聯網中，實體隸屬機構有時并不提供實體搜索定位服務，或者提供的搜索定位服務在應用范圍、精度等方面存在缺陷。基于此，在體系結構中定義了一種開放的分布式信息服務，以為不同類型、不同隸屬的實體提供搜索服務，而將這種實體搜索服務稱為實體通用搜索服務。實體通用搜索服務由分布在全局范圍內的服務器集群提供，服務器集群則由權威機構實施管理，權威機構可以將相關的管理維護權限經過審批下發給對應從屬機構。任何實體可以自由注冊通用搜索服務，注冊實體向CNS系統申請更新其尋址信息，在其尋址信息中添加實體通用搜索服務接口的URI即可。CNS服務更新后，物聯網中其他實體可以借助通用搜索服務對已注冊實體展開搜索，獲取已注冊實體的位置信息。同時，已注冊實體會自動成為通用搜索服務部署在終端層的一個偵聽器，為通用搜索服務收集偵聽到的其他實體信息。各個實體多配合參與并協助實體通用搜索服務，完成對物聯網中實體的搜索定位。實體通用搜索服務將收集到的數據信息按照區域劃分存儲在相應的服務器數據庫中，數據庫中記錄格式如表1所示。這些由終端層已注冊實體收集的數據通常具有時效性，服務器會定期刪除失效數據。

Type2：僅存儲自身的編碼以及相關靜態屬性信息，這些信息卻只能由鄰近的Type1類型實體讀取，而Type2類型實體的位置則只能通過對其發生讀取動作的Type1類型的實體位置間接確定。例如，電子標簽等。

MCOUS算法對實體的搜索定位由本地搜索和全局搜索兩部分組成。其中的本地搜索是指在發起搜索的實體所在的Ad hoc網絡范圍內搜索目標實體；全局搜索則是指通過隸屬機構提供的搜索服務和實體通用搜索服務在全局范圍內對目標實體展開搜索。用戶可以通過Type1類型的實體對目標實體同時進行本地搜索和全局搜索，或者通過互聯網直接對目標實體進行全局搜索。

2.1MCOUS算法描述

MCOUS算法中的“通用”二字含義即指算法適用于物聯網中各類型的、隸屬各機構的實體，該算法不僅適用于物聯網中具有數據處理和計算能力的智能實體的搜索定位，同樣也適用于只能支持被動讀取的電子標簽類型的實體的搜索定位。為了解決物聯網中實體類型表現各異、通信協議互不相通的問題，MCOUS算法在搜索請求消息中加入了錨點序列字段，搜索請求消息可以在不同類型實體間采用不同的通信協議轉發，轉發實體將自身的位置信息寫入錨點序列，當搜索請求消息到達目標實體時，目標實體沿反轉的錨點序列回復應答消息。“多路徑并發”就是指算法采用不通過互聯網本地搜索和通過互聯網全局搜索相結合的搜索算法來確定已知編碼實體的位置。雖然物聯網中實體數量巨大，但是具有一定計算和數據處理能力的智能實體數量有限，密度也相對稀疏，這些智能實體可能也只有一部分主動協助其他實體進行搜索請求消息的轉發和上傳，為了最大化地開發可用資源以提供穩定的搜索服務，MCOUS算法采用多路徑并發搜索的機制。多路并發機制既具有本地實體搜索定位的快速、高效、低負載的特點，也具有全局實體搜索高性能、穩定的特點。

當源實體S對目標實體D發起搜索時， 首先，S構造一個搜索請求消息MSG，搜索請求消息中的信息描述如表2所示。然后，S開始對D的搜索。具體地，如果S與互聯網相連，則S在發起對D的本地搜索定位過程的同時，也將發起一個對D的全局搜索定位過程。否則，S僅發起對D的本地搜索定位過程。其后，S在預設的搜索應答等待時間內守候來自D的搜索應答消息ACK。最后，S根據收到的不同搜索服務回應的、來自不同路徑的應答消息ACKs而成功獲取目標實體D的最準確位置信息。MCOUS算法的具體描述如下。

2.3目標實體的全局搜索定位

全局搜索定位是通過數據服務器層的實體搜索服務在全局范圍內搜索目標實體，并獲取其位置信息。發起全局搜索定位過程的實體可通過CNS系統獲得目標實體相應搜索服務的URI。如果目標實體不存在相應的搜索服務，則本次全局搜索過程結束；否則，就可通過相應搜索服務獲取目標實體位置信息。在文中，目標實體支持的搜索服務可分為兩類，即實體隸屬機構提供的搜索服務以及本文提出的實體通用搜索服務。如果目標實體所屬機構提供了實體搜索服務，那么MCOUS算法將直接利用機構提供的搜索服務獲取實體的位置信息。同時，如果目標實體已經注冊了通用搜索服務，那么MCOUS算法可以憑借通用搜索服務查詢目標實體近期被偵聽到的記錄，由記錄中偵聽實體在其所對應的Ad hoc網絡中進一步對目標實體進行搜索，獲取更為準確的實體位置信息。全局搜索的步驟描述如下。

當偵聽實體L收到MSG后，將在其所在Ad hoc網絡搜索目標實體。首先，L為MSG啟動一個計時器，設置應答等待時間。然后，L向其鄰居廣播MSG，發起對目標實體的本地搜索，等待來自目標實體的應答消息。其他實體在收到MSG后，判斷自身是否為目標實體，如果是，則向偵聽實體L回復搜索應答消息ACK；否則，將自身位置寫入MSG的錨點序列中，繼續向鄰居實體廣播MSG。在實體L的應答等待時間內，L將向發起搜索的實體S轉發其收到的搜索應答消息ACK。如果在實體L的應答等待時間內，L沒有收到來自任何實體的ACK，則說明目標實體可能目前只是支持被動讀取，不具有應答能力；或者目前Ad hoc網絡連通性較差，無法將MSG發送到目標實體。當這種情況出現時，目標實體的位置只能間接依靠偵聽實體L的具體位置來確定，此時實體L向源實體S回復一個包含其位置信息的搜索應答消息ACK。由此決定了在這種情況下，搜索結果的精確性和實效性略差。由偵聽實體L對目標實體進行搜索定位實現步驟描述如下。

算法中可以通過建立搜索請求消息緩存表來協助實體判斷是否接收過某條搜索請求消息。如果實體不對接收到的消息進行緩存，還可以根據消息中錨點序列判斷是否接收過某條搜索請求消息，具體地，如果當前實體的位置與錨點序列中某錨點位置重合（當兩個位置間的歐式距離足夠小時，即認為這兩個位置重合），則實體即可斷定曾經接收過該消息。

3仿真實驗

在NS2下對MCOUS算法進行仿真實驗，將 2 000m*2 000m的正方形區域均分為1 000m*1 000m的四個正方形區域，在每個區域內建立一個Ad hoc網絡，其中每個Ad hoc網絡中隨機分布500個實體。不同Ad hoc網絡中的實體相互獨立，互不通信。實驗中，實體數量為N=2000，其中Type1類型的實體數量為NType1，NType1中有20%的實體與互聯網相連（可以發起全局搜索的實體）。

系統中存在三種不同類型的通信協議，如表3所示。其中，Type1類型的實體具有RFID和Zigbee通信協議，同時具有IEEE 802.11通信協議的概率為25%，而Type2類型的實體只具有RFID通信協議。在本文中通過設置節點類型和通信距離來模擬各類通信協議，從而避免了三類協議之間的通信干擾[9-10]對算法性能的影響。

由圖3和圖4可知，實體搜索的成功率與物聯網中的Type1類型的實體數量成正比。由于參與轉發消息的Type1類型的實體數量增加，因此，本地Ad hoc網絡連通性增強，從而提高了本地搜索的成功率。Type1類型實體數增加不但提升了Ad hoc網絡的連通性，同時也提供了更多的與互聯網相連的實體進行目標實體的全局搜索，由此，即提高了利用實體隸屬機構提供的搜索服務和實體通用搜索服務的搜索成功率。當實體密度和數量一定時，具有實體隸屬機構提供的搜索服務的實體數量增加或具有實體通用搜索服務的實體數量增加時，搜索的成功率都將提高。

在上述拓撲結構的基礎上，每個Ad hoc網絡中的實體以RWP模型運動，運動場景與靜態場景下的MCOUS算法搜索成功率的對比結果如圖5所示。由圖5中可知，當網絡連通性較強時，靜態實體場景下和動態實體場景下的搜索成功率相近。搜索請求消息中的錨點序列，可以避免實體移動所引起的消息丟失，從而提高了搜索的成功率。

4結束語

隨著物聯網的發展，已產生了兩個技術需求正擺在眾多研究者面前：對海量實體的數據信息實現組織和存儲的體系結構；在海量實體中高效、準確地搜索及定位用戶需要的實體。為了滿足上述需求，本文首先提出一種基于地標系統的物聯網實體搜索定位的體系結構，將其分為地表層、終端層以及數據服務層三部分。該體系結構整合了各機構的實體信息和相應的信息服務，同時提出了實體可以個體身份確定注冊的實體通用搜索服務。在此基礎上，又提出了MCOUS算法，算法采用多路徑并發機制對物聯網中已知編碼的目標實體進行搜索。實驗證明，MCOUS算法可以高效、 準確地獲取目標實體的位置信息。下一步工作將在算法中加入不同粒度的搜索權限控制，具體表現在實體隱私性保護上，并且保證：

（1）攻擊者無法知曉所定位和跟蹤的人或物體；

（2）未經協議允許，定位和跟蹤即無法實現。

此外，使用者還可以得到告知自身正在被定位和跟蹤，并能有選擇地放棄該功能。

參考文獻：

[1]GERSHENFELD N， KRIKORIAN R， COHEN D. The Internet of things[J]. Scientific American， 2004， 291（4）： 76-81.

[2]ITU. ITU Internet Reports 2005： The Internet of Things [R]. Geneva， 2005.

[3]EPOSS. Internet of Things in 2020， Roadmap for the Future[R]. 2008.

[4]沈蘇彬， 范曲立， 宗平. 物聯網的體系結構與相關技術研究[J]. 南京郵電大學學報， 2009， 29（6）：1-11.

[5]COMMISSION OF THE EUROPEAN COMMUNITIES. Internet of Things -- An action plan for Europe[R]. 2009.

[6]JEFFERY K G. The Internet of Things： The Death of a Traditional Database？[J]. IETE Technical Review， 2009， 26（5）：313-319.

[7]COMMISSION OF THE EUROPEAN COMMUNITIES. Early Challenges regarding the ‘Internet of Things’[R]. Brussels， 2008.

[8]孔寧， 李曉東， 羅萬明. 物聯網資源尋址模型. 軟件學報， 2010， 21（7）：1657-1666.

[9]YOON D K， SHIN S Y， KWON W H. Packet Error Rate Analysis of IEEE 802.llb under IEEE 802.15.4 Interference[A]. Proceeding of IEEE Vehicular Technology Conference[C]. 2006，1186-1190.

[10]SHIN S Y， PARK H S， CHOI S. Packet Error Rate Analysis of ZigBee Under WLAN and Bluetooth Interferences[J]. IEEE Transactions on Wireless Communications， 2007， 6（8）： 2825–2830.