董自強，劉燦燦

(南京郵電大學 通信與信息工程學院，江蘇 南京 210000)

?

基于鄰近服務的D2D節(jié)點發(fā)現(xiàn)技術綜述

董自強，劉燦燦

(南京郵電大學 通信與信息工程學院，江蘇 南京 210000)

D2D節(jié)點發(fā)現(xiàn)技術是實現(xiàn)D2D通信首先要解決的重要問題。圍繞無架構輔助的D2D節(jié)點搜索問題，對其研究現(xiàn)狀進行了系統(tǒng)的梳理和述評，指出了該領域現(xiàn)有研究存在的問題，并綜述了相應的典型解決方案和研究成果。

D2D；節(jié)點發(fā)現(xiàn)；傳感網

引用格式：董自強，劉燦燦. 基于鄰近服務的D2D節(jié)點發(fā)現(xiàn)技術綜述[J].微型機與應用，2016,35(16)：60-62，66.

0　引言

最近幾年D2D(device-to-device)技術相當流行，它是新一代通信模式，能讓移動終端與其他終端不需要透過網絡傳遞就可實現(xiàn)相互之間的通信。但是在D2D節(jié)點(設備)建立連接之前，設備必須先發(fā)現(xiàn)其他D2D節(jié)點。節(jié)點發(fā)現(xiàn)是進行D2D通信的基礎，因此也是D2D通信的關鍵問題之一。

目前已經有很多基于鄰近服務的D2D節(jié)點發(fā)現(xiàn)技術，大體可分為有外部架構輔助和無外部架構輔助兩類[1]。本文重點說明沒有外部架構輔助的直接節(jié)點搜索的情況。

沒有外部架構輔助的D2D節(jié)點的搜索就不需要基站的參與，這樣節(jié)點的搜索就可以控制在局部范圍進行操作，而且搜索過程的復雜性也被轉移到用戶終端，所以這種方法更靈活而且伸縮性強。另外，在沒有蜂窩網絡覆蓋的情況下(意味著沒有外部架構輔助)，必須選擇這類沒有架構輔助的搜索方案。然而，如果沒有外部架構的輔助，也就意味著在沒有網絡協(xié)調的情況下，D2D設備必須在節(jié)點搜索的過程中盲目地解碼搜索信號：D2D設備需要一直發(fā)送搜尋信標，對移動設備來說這是非常耗時和耗能的。在搜索的過程中還有一些其他的挑戰(zhàn)，因此本文將詳細描述如何解決節(jié)點發(fā)現(xiàn)過程中的主要問題。

1　概述

D2D技術是新一代通信領域的研究熱點之一，D2D節(jié)點搜索是這項技術首先要解決的難點之一，也是這項技術實現(xiàn)的重點。研究表明:在搜索過程中，D2D節(jié)點的絕大部分能量消耗在空閑偵聽(Idle Listening,即節(jié)點等待接收信息)階段。而減少空閑偵聽的主要技術就是占空比(Duty Cycle)技術,即讓節(jié)點交替處于工作和休眠狀態(tài),從而節(jié)省節(jié)點能量。低占空比(Low Duty Cycle,LDC)[2]技術則讓節(jié)點絕大部分時間處于休眠狀態(tài),極少時間處于工作狀態(tài)(比如節(jié)點1%的時間處于工作狀態(tài)即蘇醒狀態(tài),其余99%的時間處于休眠狀態(tài))。在低占空比無線傳感器網絡中,由于節(jié)點長時間處于休眠狀態(tài)(比如99%的時間休眠)[3],且節(jié)點間有可能異步,因此,在沒有任何輔助設施(比如沒有定向天線、沒有同步、沒有基站、沒有GPS 等)的情況下，兩個物理鄰居節(jié)點很難同時處于蘇醒狀態(tài)并相互發(fā)現(xiàn)。此外D2D節(jié)點具有移動性等因素也使節(jié)點發(fā)現(xiàn)問題將變得更加困難。

基于以上所述，在沒有外部架構的輔助的情況下，設計出合理的節(jié)點發(fā)現(xiàn)方案顯得非常重要。本文主要關注兩種近距離網絡傳輸技術：WiFi和藍牙[4]。

本文介紹了在沒有外部設備輔助情況下D2D節(jié)點的發(fā)現(xiàn)所面臨的主要挑戰(zhàn),描述了一些能夠解決這些挑戰(zhàn)的一些典型方案，列舉了一些熱門的開放性問題。

2　挑戰(zhàn)及概念介紹

2.1主要挑戰(zhàn)

沒有外部架構的輔助，節(jié)點的搜索就可以控制在局部范圍進行操作，這使得搜索過程更靈活，然而，搜索過程的復雜性也被轉移到用戶終端。無外部架構輔助的節(jié)點搜索面臨的主要挑戰(zhàn)是能源效率、快速發(fā)現(xiàn)、異步搜索和可伸縮性。

如果沒有能耗的限制，節(jié)點發(fā)現(xiàn)就簡單多了，可以讓每臺設備周期性地發(fā)送信標以便其他設備能及時快速地發(fā)現(xiàn)它的存在。例如，假設有設備A和設備B，設備B想發(fā)現(xiàn)設備A。在沒有其他架構輔助的情況下，通常設備A會周期性地發(fā)送信標信號以便讓其他設備能發(fā)現(xiàn)它，所以設備B可以通過簡單的掃描信標信號來發(fā)現(xiàn)A[5]。然而，某種程度上來說，設備的能源效率和快速發(fā)現(xiàn)是一對矛盾。為了實現(xiàn)節(jié)點的快速發(fā)現(xiàn)，設備A需要發(fā)送的信標周期較短，這意味著消耗更多的能量，因此設備的能源效率和快速發(fā)現(xiàn)相互之間存在一個折衷。

相反，設備可以按照一定比例的占空比，在大部分時間里讓無線接口保持在休眠狀態(tài)中，并定期將其喚醒以執(zhí)行搜索任務。當然，兩個互相搜索的設備要想發(fā)現(xiàn)對方必須保持喚醒狀態(tài)，所以應該制定合適的占空比方案來確保兩個鄰近設備的喚醒時間是重疊的。通過時間的同步可以讓設備同時處于喚醒狀態(tài)，而且這并不難實現(xiàn)。然而，同步需要基礎設施的支持(4G /無線基站)，或使用車載GPS組件，但不能一直使用，因為能耗巨大。因此，在無法獲得同步時鐘且保證低占空比的情況下，為了確保鄰近設備的喚醒時間在合理的時間內重疊，不少研究人員提出了異步搜索方案。

可伸縮性：節(jié)點搜索協(xié)議應當能在高度密集的環(huán)境中正常工作。如果希望許多設備能同時被搜索到，那么所有設備將在同一時間內一同發(fā)送信標，這些信標信號的傳輸有可能導致信號流量擁塞，從而使一些設備不能發(fā)現(xiàn)。

2.2概念介紹

本文接下來將介紹幾種可以有效解決上述難題的節(jié)點搜索方案。首先需要說明節(jié)點搜索方案中常用的概念，包括：時隙、搜索周期、搜索延遲、最長搜索延遲、占空比、對稱性和非對稱性。

(1)時隙：時間被分成具有相同大小的間隔，每個時間間隔被稱為一個時隙。時隙的概念可以減少相關實驗的困難，當確保該時隙的長度大于總時鐘偏移，就可以有效地克服時鐘的偏移的影響。

(2)搜索周期：N個時隙組成一個搜索周期。在一個搜索周期內，按照某個時間表安排節(jié)點的工作狀態(tài)。

(3)搜索延遲：在彼此的通信范圍內，兩個節(jié)點從開始搜索到完成搜索所經過的時間長度。

(4)最長搜索延遲：一個節(jié)點發(fā)現(xiàn)它所有鄰居的最長延遲。它表示兩個節(jié)點在其通信范圍內確?？梢园l(fā)現(xiàn)彼此所需要的最小時長。

(5)占空比：節(jié)點從工作或睡眠狀態(tài)定期交替。一個節(jié)點的工作狀態(tài)的持續(xù)時間與總時間長度的比值稱為占空比。

(6)對稱性：節(jié)點搜索過程中時隙序列相同的調度，也就是具有相同占空比被稱為對稱。

(7)非對稱性：節(jié)點搜索過程中時隙序列不同的調度，也就是具有不同占空比被稱為非對稱[6]。

3　解決方案

根據(jù)以上提出的挑戰(zhàn)，對有關節(jié)點搜索方面的一些研究文獻總結如下。

3.1探照燈方案

節(jié)能的異步節(jié)點搜索方案可以分兩類：概率性方案和確定性方案，它們各有優(yōu)缺點。探照燈方案[7]結合了這兩種方案，在設備的能源效率和快速發(fā)現(xiàn)之間保持了平衡。具體而言，探照燈利用基于時隙的周期性搜索表，一個周期包含t個時隙，為了節(jié)約能源，設備在大多數(shù)時隙處于休眠狀態(tài)。

每個周期有兩個活動時隙：錨時隙(A)和探測時隙(P)(參見圖1，t=7)。能成功搜索到鄰近節(jié)點的情況有3種：AA重疊、PA重疊和PP重疊。一般情況下，不會發(fā)生AA重疊，因為t足夠大(為了簡化，圖1中t取值較小)，所以這里只討論另外兩種情況。

錨時隙的位置固定在每個周期的第一個時隙。如果兩個節(jié)點的周期相同，則兩個節(jié)點錨時隙的相對位置保持不變，如圖1所示，節(jié)點B的錨時隙相對于節(jié)點A總是延后4個時隙。

這種搜索法案的好處是節(jié)點只需要探測半個周期的時隙，如圖1所示，P時隙只要按照1, 2, 3，…，t/2的模式就能確保PA重疊情況的出現(xiàn)。

此外，如圖1(b)所示，P時隙不按照順序出現(xiàn)的方案叫做隨機探照燈，這種方案使PP重疊的可能性大大增加。在順序探照燈方案中(參見圖1(a))，兩個節(jié)點的P時隙遵循相同的模式，因此它們經常保持同步，大大減少了PP重疊的發(fā)生概率。隨機探照燈參照了概率性的思想，在這種方案中，P時隙可以隨機地選擇不同模式，實現(xiàn)了概率性和確定性方法的結合，比如圖1(b)中，節(jié)點A每個周期中P時隙距離A時隙延遲順序為321，節(jié)點B順序為312，顯然P時隙模式不同。

3.2群組搜索方案

群組搜索方案[8]就是將鄰近區(qū)域的設備組成一個群組，群組中的設備輪流發(fā)布組員的存在消息。因此，設備可以降低發(fā)送消息的占空比，并且具有能源效率高和可伸縮性的優(yōu)點。此外，該組中的其他設備仍能保證被快速發(fā)現(xiàn)。

這個方案的設計中有3個主要問題。首先，分散的設備如何能夠組成一個按序發(fā)送信標的群組？其次，設備是移動的，如何在移動的環(huán)境中維持這個群組？第三，形成一個群組會引進額外的能耗，這是否會使弊大于利？

對于第一個問題，該方案被分為兩個部分：加入操作和群組操作。加入操作規(guī)定設備如何選擇群組以及如何被群組接受。群組操作可以調節(jié)成員列表，比如新成員設備的添加或從列表中刪除一個成員。如圖2所示，為了實現(xiàn)這兩個操作，引入了3個窗：加入窗、聯(lián)系窗和更新窗。加入窗可以發(fā)現(xiàn)其他設備，聯(lián)系窗可以進行3次握手，更新窗可以通知其他設備已更新的成員列表。

圖2　信標發(fā)送模式

對于第二個問題，該方案引入了增強技術。在移動環(huán)境中，成員設備可能頻繁地移動出群組通信范圍。因此，群組可能經常重組，這會導致程序崩潰，而且這也不符合能源效率和可擴展性的要求。如圖2所示，增強技術就是假設A沒有收到B的ACK消息(B的更新窗發(fā)送)，A將另外發(fā)送一個信標給C，從而降低群組斷鏈重組的頻率。

對于第三個問題，該方案只需要設備保持低占空比，而且隨著群組成員數(shù)量的不斷增加，占空比將不斷降低。

3.3藍牙與WiFi搜索的融合

WiFi和藍牙技術在節(jié)點搜索中各有優(yōu)缺點。WiFi覆蓋范圍大但能耗也大，而藍牙能耗雖小但覆蓋范圍也小。為了節(jié)省能量，而又不減小設備的搜索范圍，可以采用CQuest搜索方案[9]。

移動節(jié)點會形成臨時集群，如圖3(a)所示，每個集群成員可以通過WiFi搜索到距離較遠的另一個集群的所有成員。因此，如圖3(b)所示，CQuest方案是讓每個集群成員采用功耗更低的藍牙搜索，而只保留其中一個成員的WiFi搜索。

圖3　節(jié)點集群搜索方式

CQuest由三個部分組成。

(1)每個集群只有選定的設備需要使用WiFi和藍牙掃描，其他設備只使用藍牙掃描。這個WiFi設備選擇的基本思路是：每個集群設備檢查是否有其他成員會在下一輪進行WiFi掃描，如果有，該節(jié)點下一輪就不進行WiFi掃描，否則，該節(jié)點下一輪開始掃描。這顯然會產生競爭，CQuest提供了詳細的解決方案，這里不再闡述。

(2)關于每一輪掃描時間的確定，對于有架構輔助的同步網絡，該方案可以使用有固定周期的信標，一輪時間就可以定義為固定數(shù)目的周期。對于異步網絡，可以使用現(xiàn)有的異步鄰居發(fā)現(xiàn)協(xié)議。

(3)維持CQuest集群。每個集群成員都有一份集群成員名單列表，所以只要保持它們的列表同步。一旦有節(jié)點加入集群，其他成員的列表都會被更新。CQuest使用兩個閾值來確定是否有成員離開集群。

4　開放性研究問題

在D2D節(jié)點發(fā)現(xiàn)的過程中，依舊存在著一些研究問題。

4.1網絡輔助和定位

利用定位技術和網絡云的輔助，可以有效提高節(jié)點搜索效率，例如網絡服務器可根據(jù)節(jié)點所在位置分析出周圍是否存在可搜索節(jié)點，若沒有，則關閉節(jié)點搜索開關，從而提高搜索效率[10-11]。

4.2節(jié)點搜索與服務發(fā)現(xiàn)的結合

D2D節(jié)點搜索的目的是為了發(fā)現(xiàn)并傳輸服務，傳統(tǒng)的服務發(fā)現(xiàn)方法是搜索到節(jié)點后必須建立連接才可以獲知服務基本信息。例如，WiFi聯(lián)盟提出了WiFi Direct技術，該技術在節(jié)點搜索的信號中添加了服務信息，實現(xiàn)了節(jié)點搜索與服務發(fā)現(xiàn)的結合，使節(jié)點不需要建立連接就可獲得服務基本信息[12]。

5　結論

D2D節(jié)點發(fā)現(xiàn)是D2D通信的重要部分，雖然目前提出了不少解決方案，但是性能上還有很大的提高空間。本文闡述了D2D節(jié)點搜索中的主要問題，針對這些問題總結了一些有代表性的解決方案，最后，列舉了一些熱門的開放性問題。

[1] Lei Lei, Zhong Zhangdui, Lin Chuang, et al. Operator controlled device-to-device communications in LTE-advanced networks[J]. IEEE Wireless Communications, 2012, 19(3): 96-104.

[2] Gu Yu, He Tian. Data forwarding in extremely low duty-cycle sensor networks with unreliable communication links[C].Proceedings of the 5th International Conference on Embedded Networked Sensor Systems, ACM, 2007,19(7): 321-334.

[3] 陳良銀, 顏秉姝, 張靖宇, 等. 移動低占空比傳感網鄰居發(fā)現(xiàn)算法[J]. 軟件學報, 2014, 25(6): 1352-1368.

[5] KRAVETS R H. Enabling social interactions off the grid[J]. Pervasive Computing, IEEE, 2012, 11(2): 8-11.

[6] Shang Tao. A comparison between neighbour discovery protocols in low duty-cycled wireless sensor networks[J]. International Journal of Computer Science and Mobile Computing, 2015,4(2):265-271.

[7] BAKHT M, TROWER M, KRAVETS R. Searchlight: helping mobile devices find their neighbors[C].Proceedings of the 3rd ACM SOSP Workshop on Networking, Systems, and Applications on Mobile Handhelds, ACM, 2011,45(3):71-76.

[8] HUANG P K, QI E, PARK M, et al. Energy efficient and scalable device-to-device discovery protocol with fast discovery[C].2013 10th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), IEEE, 2013: 1-9.

[9] BAKHT M, CARLSON J, LOEB A, et al. United we find: enabling mobile devices to cooperate for efficient neighbor discovery[C].Proceedings of the Twelfth Workshop on Mobile Computing Systems & Applications, ACM, 2012: 1-6.

[10] PRASAD A, KUNZ A, VELEV G, et al. Energy efficient D2D discovery for proximity services in 3GPP LTE-advanced Networks[J].IEEE Vehicular Technology Magezine,2014,9(3):40-50.

[11] PYATTAEV A, GALININA O, JOHNSSON K, et al. Network-assisted D2D over WiFi direct[C].Smart Device to Smart Device Communication, Springer International Publishing, 2014: 165-218.

[12] CAMPS-MUR D, GARCIA-SAAVEDRA A, SERRANO P. Device-to-device communications with Wi-Fi direct: overview and experimentation[J]. Wireless Communications, IEEE, 2013, 20(3): 96-104.

A survey of peer discovery in D2D based proximity service

Dong Ziqiang, Liu Cancan

(College of Communication and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210000, China)

D2D (device-to-device) peer discovery technology is an firstly important issue to achieve D2D communication. This paper reviewed and commented systematically for D2D peer discovery without infrastructure support, pointed out the existing problems in research of this field, and reviewed the corresponding typical solutions and research.

device-to-device; peer discovery; sensor network

TN92；TP3

A

10.19358/j.issn.1674- 7720.2016.16.018

2016-03-24)

董自強(1990-)，通信作者，男，碩士研究生，主要研究方向:D2D節(jié)點與服務的發(fā)現(xiàn)。E-mail:971820909@qq.com。

劉燦燦(1989-)，女，碩士研究生，主要研究方向：D2D節(jié)點與服務的發(fā)現(xiàn)。