董自強，劉燦燦
　　（南京郵電大學 通信與信息工程學院，江蘇 南京 210000）

       摘要：D2D節點發現技術是實現D2D通信首先要解決的重要問題。圍繞無架構輔助的D2D節點搜索問題，對其研究現狀進行了系統的梳理和述評，指出了該領域現有研究存在的問題，并綜述了相應的典型解決方案和研究成果。
　　關鍵詞： D2D；節點發現；傳感網　　

0引言
　　最近幾年D2D(devicetodevice)技術相當流行，它是新一代通信模式，能讓移動終端與其他終端不需要透過網絡傳遞就可實現相互之間的通信。但是在D2D節點（設備）建立連接之前，設備必須先發現其他D2D節點。節點發現是進行D2D通信的基礎，因此也是D2D通信的關鍵問題之一。
　　目前已經有很多基于鄰近服務的D2D節點發現技術，大體可分為有外部架構輔助和無外部架構輔助兩類［1］。本文重點說明沒有外部架構輔助的直接節點搜索的情況。
　　沒有外部架構輔助的D2D節點的搜索就不需要基站的參與，這樣節點的搜索就可以控制在局部范圍進行操作，而且搜索過程的復雜性也被轉移到用戶終端，所以這種方法更靈活而且伸縮性強。另外，在沒有蜂窩網絡覆蓋的情況下（意味著沒有外部架構輔助），必須選擇這類沒有架構輔助的搜索方案。然而，如果沒有外部架構的輔助，也就意味著在沒有網絡協調的情況下，D2D設備必須在節點搜索的過程中盲目地解碼搜索信號：D2D設備需要一直發送搜尋信標，對移動設備來說這是非常耗時和耗能的。在搜索的過程中還有一些其他的挑戰，因此本文將詳細描述如何解決節點發現過程中的主要問題。
1概述
　　D2D技術是新一代通信領域的研究熱點之一，D2D節點搜索是這項技術首先要解決的難點之一，也是這項技術實現的重點。研究表明:在搜索過程中，D2D節點的絕大部分能量消耗在空閑偵聽(Idle Listening,即節點等待接收信息)階段。而減少空閑偵聽的主要技術就是占空比(Duty Cycle)技術,即讓節點交替處于工作和休眠狀態,從而節省節點能量。低占空比(Low Duty Cycle,LDC)［2］技術則讓節點絕大部分時間處于休眠狀態,極少時間處于工作狀態(比如節點1%的時間處于工作狀態即蘇醒狀態,其余99%的時間處于休眠狀態)。在低占空比無線傳感器網絡中,由于節點長時間處于休眠狀態(比如99%的時間休眠)［3］,且節點間有可能異步,因此,在沒有任何輔助設施(比如沒有定向天線、沒有同步、沒有基站、沒有GPS 等)的情況下，兩個物理鄰居節點很難同時處于蘇醒狀態并相互發現。此外D2D節點具有移動性等因素也使節點發現問題將變得更加困難。
　　基于以上所述，在沒有外部架構的輔助的情況下，設計出合理的節點發現方案顯得非常重要。本文主要關注兩種近距離網絡傳輸技術：WiFi和藍牙［4］。
　　本文介紹了在沒有外部設備輔助情況下D2D節點的發現所面臨的主要挑戰,描述了一些能夠解決這些挑戰的一些典型方案，列舉了一些熱門的開放性問題。
2挑戰及概念介紹
　　2.1主要挑戰
　　沒有外部架構的輔助，節點的搜索就可以控制在局部范圍進行操作，這使得搜索過程更靈活，然而，搜索過程的復雜性也被轉移到用戶終端。無外部架構輔助的節點搜索面臨的主要挑戰是能源效率、快速發現、異步搜索和可伸縮性。
　　如果沒有能耗的限制，節點發現就簡單多了，可以讓每臺設備周期性地發送信標以便其他設備能及時快速地發現它的存在。例如，假設有設備A和設備B，設備B想發現設備A。在沒有其他架構輔助的情況下，通常設備A會周期性地發送信標信號以便讓其他設備能發現它，所以設備B可以通過簡單的掃描信標信號來發現A［5］。然而，某種程度上來說，設備的能源效率和快速發現是一對矛盾。為了實現節點的快速發現，設備A需要發送的信標周期較短，這意味著消耗更多的能量，因此設備的能源效率和快速發現相互之間存在一個折衷。
　　相反，設備可以按照一定比例的占空比，在大部分時間里讓無線接口保持在休眠狀態中，并定期將其喚醒以執行搜索任務。當然，兩個互相搜索的設備要想發現對方必須保持喚醒狀態，所以應該制定合適的占空比方案來確保兩個鄰近設備的喚醒時間是重疊的。通過時間的同步可以讓設備同時處于喚醒狀態，而且這并不難實現。然而，同步需要基礎設施的支持（4G /無線基站），或使用車載GPS組件，但不能一直使用，因為能耗巨大。因此，在無法獲得同步時鐘且保證低占空比的情況下，為了確保鄰近設備的喚醒時間在合理的時間內重疊，不少研究人員提出了異步搜索方案。
　　可伸縮性：節點搜索協議應當能在高度密集的環境中正常工作。如果希望許多設備能同時被搜索到，那么所有設備將在同一時間內一同發送信標，這些信標信號的傳輸有可能導致信號流量擁塞，從而使一些設備不能發現。
　　2.2概念介紹
　　本文接下來將介紹幾種可以有效解決上述難題的節點搜索方案。首先需要說明節點搜索方案中常用的概念，包括：時隙、搜索周期、搜索延遲、最長搜索延遲、占空比、對稱性和非對稱性。
　　(1)時隙：時間被分成具有相同大小的間隔，每個時間間隔被稱為一個時隙。時隙的概念可以減少相關實驗的困難，當確保該時隙的長度大于總時鐘偏移，就可以有效地克服時鐘的偏移的影響。
　　(2)搜索周期：N個時隙組成一個搜索周期。在一個搜索周期內，按照某個時間表安排節點的工作狀態。
　　(3)搜索延遲：在彼此的通信范圍內，兩個節點從開始搜索到完成搜索所經過的時間長度。
　　(4)最長搜索延遲：一個節點發現它所有鄰居的最長延遲。它表示兩個節點在其通信范圍內確保可以發現彼此所需要的最小時長。
　　(5)占空比：節點從工作或睡眠狀態定期交替。一個節點的工作狀態的持續時間與總時間長度的比值稱為占空比。
　　(6)對稱性：節點搜索過程中時隙序列相同的調度，也就是具有相同占空比被稱為對稱。
　　(7)非對稱性：節點搜索過程中時隙序列不同的調度，也就是具有不同占空比被稱為非對稱［6］。
3解決方案
　　根據以上提出的挑戰，對有關節點搜索方面的一些研究文獻總結如下。
　　3.1探照燈方案
　　節能的異步節點搜索方案可以分兩類：概率性方案和確定性方案，它們各有優缺點。探照燈方案［7］結合了這兩種方案，在設備的能源效率和快速發現之間保持了平衡。具體而言，探照燈利用基于時隙的周期性搜索表，一個周期包含t個時隙，為了節約能源，設備在大多數時隙處于休眠狀態。
　　每個周期有兩個活動時隙：錨時隙（A）和探測時隙（P）（參見圖1，t=7）。能成功搜索到鄰近節點的情況有3種：AA重疊、PA重疊和PP重疊。一般情況下，不會發生AA重疊，因為t足夠大（為了簡化，圖1中t取值較小），所以這里只討論另外兩種情況。

　　　　錨時隙的位置固定在每個周期的第一個時隙。如果兩個節點的周期相同，則兩個節點錨時隙的相對位置保持不變，如圖1所示，節點B的錨時隙相對于節點A總是延后4個時隙。
　　這種搜索法案的好處是節點只需要探測半個周期的時隙，如圖1所示，P時隙只要按照1, 2, 3，…，t/2的模式就能確保PA重疊情況的出現。
　　此外，如圖1(b)所示，P時隙不按照順序出現的方案叫做隨機探照燈，這種方案使PP重疊的可能性大大增加。在順序探照燈方案中（參見圖1(a)），兩個節點的P時隙遵循相同的模式，因此它們經常保持同步，大大減少了PP重疊的發生概率。隨機探照燈參照了概率性的思想，在這種方案中，P時隙可以隨機地選擇不同模式，實現了概率性和確定性方法的結合，比如圖1(b)中，節點A每個周期中P時隙距離A時隙延遲順序為321，節點B順序為312，顯然P時隙模式不同。
　　3.2群組搜索方案
　　群組搜索方案［8］就是將鄰近區域的設備組成一個群組，群組中的設備輪流發布組員的存在消息。因此，設備可以降低發送消息的占空比，并且具有能源效率高和可伸縮性的優點。此外，該組中的其他設備仍能保證被快速發現。
　　這個方案的設計中有3個主要問題。首先，分散的設備如何能夠組成一個按序發送信標的群組？其次，設備是移動的，如何在移動的環境中維持這個群組？第三，形成一個群組會引進額外的能耗，這是否會使弊大于利？
　　對于第一個問題，該方案被分為兩個部分：加入操作和群組操作。加入操作規定設備如何選擇群組以及如何被群組接受。群組操作可以調節成員列表，比如新成員設備的添加或從列表中刪除一個成員。如圖2所示，為了實現這兩個操作，引入了3個窗：加入窗、聯系窗和更新窗。加入窗可以發現其他設備，聯系窗可以進行3次握手，更新窗可以通知其他設備已更新的成員列表。
　　

　　對于第二個問題，該方案引入了增強技術。在移動環境中，成員設備可能頻繁地移動出群組通信范圍。因此，群組可能經常重組，這會導致程序崩潰，而且這也不符合能源效率和可擴展性的要求。如圖2所示，增強技術就是假設A沒有收到B的ACK消息（B的更新窗發送），A將另外發送一個信標給C，從而降低群組斷鏈重組的頻率。
　　對于第三個問題，該方案只需要設備保持低占空比，而且隨著群組成員數量的不斷增加，占空比將不斷降低。
　　3.3藍牙與WiFi搜索的融合
　　WiFi和藍牙技術在節點搜索中各有優缺點。WiFi覆蓋范圍大但能耗也大，而藍牙能耗雖小但覆蓋范圍也小。為了節省能量，而又不減小設備的搜索范圍，可以采用CQuest搜索方案［9］。
　　移動節點會形成臨時集群，如圖3(a)所示，每個集群成員可以通過WiFi搜索到距離較遠的另一個集群的所有成員。因此，如圖3(b)所示，CQuest方案是讓每個集群成員采用功耗更低的藍牙搜索，而只保留其中一個成員的WiFi搜索。
　　

　　CQuest由三個部分組成。
　　（1）每個集群只有選定的設備需要使用WiFi和藍牙掃描，其他設備只使用藍牙掃描。這個WiFi設備選擇的基本思路是：每個集群設備檢查是否有其他成員會在下一輪進行WiFi掃描，如果有，該節點下一輪就不進行WiFi掃描，否則，該節點下一輪開始掃描。這顯然會產生競爭，CQuest提供了詳細的解決方案，這里不再闡述。
　　（2）關于每一輪掃描時間的確定，對于有架構輔助的同步網絡，該方案可以使用有固定周期的信標，一輪時間就可以定義為固定數目的周期。對于異步網絡，可以使用現有的異步鄰居發現協議。
　　（3）維持CQuest集群。每個集群成員都有一份集群成員名單列表，所以只要保持它們的列表同步。一旦有節點加入集群，其他成員的列表都會被更新。CQuest使用兩個閾值來確定是否有成員離開集群。
4開放性研究問題
　　在D2D節點發現的過程中，依舊存在著一些研究問題。
　　4.1網絡輔助和定位
　　利用定位技術和網絡云的輔助，可以有效提高節點搜索效率，例如網絡服務器可根據節點所在位置分析出周圍是否存在可搜索節點，若沒有，則關閉節點搜索開關，從而提高搜索效率 ［1011］。
　　4.2節點搜索與服務發現的結合
　　D2D節點搜索的目的是為了發現并傳輸服務，傳統的服務發現方法是搜索到節點后必須建立連接才可以獲知服務基本信息。例如，WiFi聯盟提出了WiFi Direct技術，該技術在節點搜索的信號中添加了服務信息，實現了節點搜索與服務發現的結合，使節點不需要建立連接就可獲得服務基本信息［12］。
5結論
　　D2D節點發現是D2D通信的重要部分，雖然目前提出了不少解決方案，但是性能上還有很大的提高空間。本文闡述了D2D節點搜索中的主要問題，針對這些問題總　　結了一些有代表性的解決方案，最后，列舉了一些熱門的開放性問題。
　　參考文獻
　　［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］ 陳良銀, 顏秉姝, 張靖宇, 等. 移動低占空比傳感網鄰居發現算法［J］. 軟件學報, 2014, 25(6): 13521368.
　　［4］ PITKNEN M, KRKKINEN T, OTT J. Mobility and service discovery in opportunistic networks［C］.2012 IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOM Workshops), IEEE, 2012: 204210.
　　［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,