董自强，刘灿灿
　　（南京邮电大学 通信与信息工程学院，江苏 南京 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,