大規模物聯網中多層次立體異構網絡拓撲研究

顧磊+黃輝林+錢昕

摘要：物聯網中的多層次立體異構網絡可以將機器所產生的數據局部收集至數據采集器并連接到基礎設施網絡和云端，為用戶提供基于物聯網的智慧信息服務。針對多層次異構網絡的模型HetNet，給出了多層次立體異構網絡模型 HetNet的時間延遲閉合式的一般情形。結果表明通過布置高效率數據采集器，信息可以從機器傳輸到云端，從而大幅降低平均延遲。這為下一代無線服務提供商的多層次異構物聯網網絡的設計提供了有力的支持。

關鍵詞： 物聯網;多層次立體異構網絡;數據采集器;時間延遲

Abstract： In the machine-to-machine multilayer heterogeneous network， the data produced by a machine can be constellated to data aggregators and connected to the infrastructure network and cloud terminal. This can provide the intelligence information service based on the Internet of Things to the users. In this paper， our mathematical analysis provides general analytical closed-form end-to-end delay of HetNet， the model of multilayer heterogeneous network. The results show that by the arrangement of the high-efficiency data aggregator， the information can be sent from machine to cloud terminal and greatly reduce average delay. It also provides strong support for the design of multilayer heterogeneous network of wireless network service provider of next generation.

Key words： machine-to-machine; multi-layer heterogeneous network architecture; data aggregator; time delay

中圖分類號：TP393 ? ?文獻標志碼：A ? 文章編號：1009-6868 （2014） 06-0048-04

物聯網[1-7]指的是物與物間互相通信的網絡，第三代合作伙伴計劃（3GPP）也針對基于云服務的物聯網通信發起了專門的會話[8-10]。然而現有的組織網絡拓撲如點對點自組織網絡在大規模網絡情況下延遲嚴重[11]。因此基于大規模物聯網設計一種能夠實現高魯棒性并能節約帶寬和能源的網絡拓撲結構就顯得至關重要。

在文獻[12]中，顧磊等人利用社會網絡的方法構造了大規模物聯網中多層次立體異構網絡。他們提出為了克服傳統網絡架構所帶來的延遲缺陷，服務提供商如移動運營商可以利用數據采集器（DA）進行網絡優化。機器所產生的數據在局部被DA所收集，并且連接到基礎設施網絡和云端。這種多層次和多類型通信設備的網絡結構就是多層次立體異構網絡，如圖1所示。多層次立體異構網絡的底層是一些具有短距離通信能力的機器，上層是基礎設施和云端，而中間層則是均勻分布在空間中的DA，這種多層次立體異構網絡拓撲的物聯網能夠將機器的數據和云端的人工智能完美地結合在一起。進一步的研究結果表明[12]，多層次立體異構網絡在智慧城市的10億級別的超大規模物聯網中的時間延遲相較于點對點自組織網絡可以縮短95%。

1 大規模物聯網傳輸架構

在大型的機器（傳感器）群落中，單個機器的能量是有限的，傳輸距離和速度會受到極大的限制，信息傳遞采用自組織、多跳或點對點的方式。因此這種單一層次點對點自組織的網絡結構是物聯網最基本的形態，整個網絡沒有固定的基礎設施，每個節點都是移動的，并且都能以任意方式動態地保持與其他節點的聯系。在這種網絡中，由于終端無線覆蓋取值范圍的有限性，兩個無法直接進行通信的用戶終端可以借助其他節點進行分組轉發，同時每個終端的傳輸半徑比較狹小，因而需要多次傳遞才能從發起端將信息傳遞到目標端，并且每個終端都被賦予了各自的功能，僅有少量能量是用于傳輸信息，因而傳輸的速率也受到了限制。

根據這些微觀特性，這種單一層次的點對點自組織網絡模型可以描述為：在單位平面上均勻分布 n 個機器，其分布服從泊松生成過程;每個機器能和半徑r以內的機器相連，近似的泊松生成過程的每個點都和距離r以內的點有邊相連;所構成的點和邊的集合就是所對應的點對點自組織網絡模型，這個模型也被稱為隨機幾何圖（GRG）[13]。需要注意這里頂點的生成和空間的分布都是隨機的，因此所對應圖也是隨機。最新的研究結果[11-12]表明，當機器數量[n→∞]時，點對點自組織網絡模型的最大延遲和平均延遲都是[Θ（1/r）]。特別當物聯網滿足[r～logn/n]，則最大延遲和平均延遲都是[Θ（n/logn）]。因此這種網絡拓撲在傳輸速度和傳輸范圍上的缺陷就會造成在利用人工智能和云計算的協作上出現故障。為了克服這個缺陷并利用物聯網給人類帶來更好的服務，服務提供商如移動運營商可以利用數據采集器對網絡傳輸進行優化和加速。這種多層次和多類型通信設備的網絡結構就是多層次立體異構網絡模型HetNet [12]，如圖2所示。多層次立體異構網絡模型的底層是機器群落，上層是能夠連接到基礎設施的數據采集器網絡。機器群落由GRG（n，r）描述。我們進一步地將[[0，1]×[0，1]]單位平面平分為[m×m]塊。并且每一塊中央都放置數據采集器。每個數據采集器隨機連接k個機器。這里的參數 m 是用于度量數據采集器數量和密度，而參數k則代表單個數據采集器容量。在文獻[12]中，顧磊等人證明了在k = 1的特殊情形下，多層次立體異構網絡模型的平均延遲都是[Θ（1/mr+m）]。然而對于一般的k > 1的情況，目前還缺乏精確的數學分析結果，僅有通過數值模擬的經驗公式。在下一節我們將針對一般的k進行分析并給出多層次立體異構網絡模型平均延遲的一般閉合式分析表達式。

2 多層次立體異構網絡

模型分析

在第1節中我們給出了多層次立體異構網絡模型HetNet，在本節中將給針對該模型進行理論分析，并且對于一般k > 1的情況給出網絡延遲的閉合表達式。

首先需要計算從機器D的歐氏距離。U（[S]） 為[S]上的均勻分布，[S]是[Rk]的一個連通子集，[?] 表示歐氏距離，而E表示平均期望。令二維隨機變量[X]表示DA在[1/m×1/m]塊內的位置，而二維隨機變量 [Y1，Y2，...Yk]表示機器的位置。則可以得到關于歐式平均距離的引理：

如果隨機變量 [Y1，Y2，...Yk～] U （[[-a/2，a/2]×[-a/2，a/2]]），則有：

E[（mini=1...k）Yi=Θ（a2k！！/（2k+1）！！）] （1）

如圖3所示，令區域A為半徑[2a]、圓心在（0，0）的圓盤，而B為半徑[a2]、圓心在（0，0）的圓盤。

由簡單的微積分就可以看到，如果[Y'1，Y'2，...Y'k～]U（A）以及[Y+1，Y+2，...Y+k～]U（B），則有：

給定[Y1，Y2，...Yk]的位置，令區域D=[[-a/2，a/2]×[-a/2，a/2]]，由于A[?]D 而且平均距離在小范圍內更小，因此可得出：

E[（mini=1...k）Yi≥] E[（mini=1...k）Y+i] ?（3）

上界估計也類似可得，綜合即得到不等式（2）。再根據極坐標積分變化就得到：

以及

E[（mini=1...k）Y+i=aπ2k！！/（2k+1）！！] ? （5）

這里[2k！！=2k（2k-2）（2k-4）...1]。

結合式（1）和式（5）可以得到多層次立體異構網絡模型HetNet的對于一般k > 1的網絡平均延遲。

多層次立體異構網絡模型HetNet的對于一般k > 1的平均網絡延遲是[Θ（2k！！/mr（2k+1）！！+m）]。由于機器之間的傳輸距離是r 而且單位平面平分為[m×m]塊，每塊的大小是 [1/m×1/m]，可以得到機器到DA的時間延遲是[O（2k！！/mr（2k+1）！！）]，并由于機器到機器的延遲可以分解為機器到DA、DA到DA和DA到機器，而DA到DA之間的平均延遲是[2m/3]，我們就可以直接得到網絡平均延遲的上界估計為[O（2k！！/mr（2k+1）！！+m）]。下界估計則采用文獻[12]中的定理3的估計技巧，即對于任意小[ε>0]，至少[（1-ε）n（n-1）/2] 點對的最短路徑是通過數據采集器的，由此可得所需結果。

圖4給出了系統中機器數量n = 5 000，r = 0.04時，不同參數m和k的時間延遲的數值模擬結果。

這里的參數m是用于度量DA的數量和密度，而參數k則代表單個DA容量。可以看到在研究多層次立體異構網絡模型HetNet中，隨著m的增大，平均時間延遲先減小后增大。而隨著DA容量k的提高，機器到DA平均延遲可以大幅度縮短。實際上DA的數量以及單個DA的容量是決定底層機器和DA之間傳輸的關鍵參數。而通過這些DA，信息可以搭乘“高速公路”，從而大幅降低平均延遲，這也為下一代無線服務提供商的多層次異構物聯網網絡的設計提供了有力的支持。

3結束語

物聯網中的多層次異構網絡可以將機器所產生的數據局部收集至DA，并且連接到基礎設施網絡和云端，為用戶提供基于物聯網的智慧信息服務。

在文獻[12]中，顧磊等人提出了針對多層次異構網絡的模型 HetNet并給出了在k = 1的特殊情形下，多層次立體異構網絡模型的平均延遲的閉合式分析表達式 [Θ（1/mr+m）]。然而對于一般k > 1的情況，目前還缺乏精確的數學分析結果，僅有通過數值模擬的經驗公式。文章對于一般k > 1情況的給出了多層次立體異構網絡模型的平均延遲閉合式的分析表達式[Θ（2k！！/mr（2k+1）！！+m）]，這意味著隨著DA容量k的提高，機器到DA平均延遲可以大幅度縮短。

參考文獻

[1] LIEN S Y， CHEN K C， LIN Y. Toward ubiquotous massive access in 3GPP machine-to-machine communications in 3GPP [J]. IEEE Commun. Mag.， 2011， 49（4）： 66-74. doi： 10.1109/MCOM.2011.5741148.

[2] LIEN S Y， CHEN K C. Massive access management for QoS guarantees in 3GPP machine-to-machine communications [J]. IEEE Commun. Lett.， 2011， 15（3）： 311-313. doi： 10.1109/LCOMM.2011.011811.101798.

[3] LIEN S Y， LIAU T H， KAO C Y， CHEN K C. Cooperative access class barring for machine-to-machine communications [J]. IEEE Trans.Wireless Commun.， 2012， 11（1）： 27-32. doi： 10.1109/.TWC.2011.111611.110350.

[4] ZHENG K ， HU F ，WANG W， XIANG W， DOHLER M. Radio resource allocation in LTE-advanced cellular networks with M2M communications[J]. IEEE Commun. Mag.， 2012， 50（6）： 184-192. doi： 10.1109/MCOM.2012.6231296.

[5] KWON T， CHOI J W. Multi-group random access resource allocation for M2M devices in multicell systems [J]. IEEE Commun. Lett.， 2012， 16（6）： 834-837.

[6] NIYATO D， XIAO L， WANG P. Machine-to-machine communication for home energy management system in smart grid [J]. IEEE Commun. Mag.， 2011， 49（4）： 53-59. doi： 10.1109/MCOM.2011.5741146.

[7] CHEN K C， LIEN S Y. Machine-to-machine communications： technologies and challenges [J]. Ad Hoc Networks， 2014， 18： 3-23. doi： 10.1016/j.adhoc.2013.03.007.

[8] 3GPP. TR 22.868 Study on facilitating machine to machine， 3rd Generation Partnership Project （3GPP）[S]. 2009.

[9] 3GPP. TR 22.368 Service requirements for machine-type communications， 3rd Generation Partnership Project （3GPP） [S]. 2009.

[10] 3GPP. TR 23.888 System improvement for machine-type communications， 3rd Generation Partnership Project （3GPP） [S]. 2009.

[11] LIN S C， GU L and CHEN K C. Providing statistical QoS guarantees in large cognitive machine-to-machine networks[C]// IEEE GLOBECOM Workshop on M2M， Anaheim， CA. 2012： 1700-1705. doi： 10.1109/GLOCOMW.2012.6477841.

[12] GU L， LIN S C， CHEN K C. Small-world networks empowered large machine-to-machine communications[C]// IEEE Wireless Communication and Networking Conference（WCNC）， Shanghai， China. 2013： 1558-1563. doi： 10.1109/WCNC.2013.6554795.

[13] PENROSE M. Random Geometric Graphs（Oxford Studies in Probability）[M]. Oxford： Oxford University Press. 2005.

[5] KWON T， CHOI J W. Multi-group random access resource allocation for M2M devices in multicell systems [J]. IEEE Commun. Lett.， 2012， 16（6）： 834-837.

[6] NIYATO D， XIAO L， WANG P. Machine-to-machine communication for home energy management system in smart grid [J]. IEEE Commun. Mag.， 2011， 49（4）： 53-59. doi： 10.1109/MCOM.2011.5741146.

[7] CHEN K C， LIEN S Y. Machine-to-machine communications： technologies and challenges [J]. Ad Hoc Networks， 2014， 18： 3-23. doi： 10.1016/j.adhoc.2013.03.007.

[8] 3GPP. TR 22.868 Study on facilitating machine to machine， 3rd Generation Partnership Project （3GPP）[S]. 2009.

[9] 3GPP. TR 22.368 Service requirements for machine-type communications， 3rd Generation Partnership Project （3GPP） [S]. 2009.

[10] 3GPP. TR 23.888 System improvement for machine-type communications， 3rd Generation Partnership Project （3GPP） [S]. 2009.

[11] LIN S C， GU L and CHEN K C. Providing statistical QoS guarantees in large cognitive machine-to-machine networks[C]// IEEE GLOBECOM Workshop on M2M， Anaheim， CA. 2012： 1700-1705. doi： 10.1109/GLOCOMW.2012.6477841.

[12] GU L， LIN S C， CHEN K C. Small-world networks empowered large machine-to-machine communications[C]// IEEE Wireless Communication and Networking Conference（WCNC）， Shanghai， China. 2013： 1558-1563. doi： 10.1109/WCNC.2013.6554795.

[13] PENROSE M. Random Geometric Graphs（Oxford Studies in Probability）[M]. Oxford： Oxford University Press. 2005.

[5] KWON T， CHOI J W. Multi-group random access resource allocation for M2M devices in multicell systems [J]. IEEE Commun. Lett.， 2012， 16（6）： 834-837.

[6] NIYATO D， XIAO L， WANG P. Machine-to-machine communication for home energy management system in smart grid [J]. IEEE Commun. Mag.， 2011， 49（4）： 53-59. doi： 10.1109/MCOM.2011.5741146.

[7] CHEN K C， LIEN S Y. Machine-to-machine communications： technologies and challenges [J]. Ad Hoc Networks， 2014， 18： 3-23. doi： 10.1016/j.adhoc.2013.03.007.

[8] 3GPP. TR 22.868 Study on facilitating machine to machine， 3rd Generation Partnership Project （3GPP）[S]. 2009.

[9] 3GPP. TR 22.368 Service requirements for machine-type communications， 3rd Generation Partnership Project （3GPP） [S]. 2009.

[10] 3GPP. TR 23.888 System improvement for machine-type communications， 3rd Generation Partnership Project （3GPP） [S]. 2009.

[11] LIN S C， GU L and CHEN K C. Providing statistical QoS guarantees in large cognitive machine-to-machine networks[C]// IEEE GLOBECOM Workshop on M2M， Anaheim， CA. 2012： 1700-1705. doi： 10.1109/GLOCOMW.2012.6477841.

[12] GU L， LIN S C， CHEN K C. Small-world networks empowered large machine-to-machine communications[C]// IEEE Wireless Communication and Networking Conference（WCNC）， Shanghai， China. 2013： 1558-1563. doi： 10.1109/WCNC.2013.6554795.

[13] PENROSE M. Random Geometric Graphs（Oxford Studies in Probability）[M]. Oxford： Oxford University Press. 2005.