Partial Delaunay triangulation and degree limited localized Bluetooth scatternet formation
Partial Delaunay triangulation and degree limited localized Bluetooth scatternet formation
复制标题
DOI：
10.1109/tpds.2004.1271184
复制
发表时间：
2004-04
影响因子：
5.3
通讯作者：
Xiangyang Li;I. Stojmenovic;Yang Wang
中科院分区：
文献类型：
--
作者：
Xiangyang Li;I. Stojmenovic;Yang Wang
我们解决的问题，本地化的scatternet形成多跳蓝牙为基础的个人区域ad hoc网络。假设节点知道它们的位置，并且能够在邻居发现阶段中与位于它们的传输半径内的任何它们的邻居节点建立连接。所提出的形成算法的下一阶段是可选的，并且可以应用于以局部化方式构造稀疏几何结构。我们提出了一种新的稀疏平面结构，即部分Delaunay三角剖分（PDT），它可以局部构造，比其他已知的局部平面结构更密集。在下一个强制性阶段，通过应用Yao结构将每个节点的度限制为7，并且在所创建的子图中形成微微网中的主从关系。此阶段由几个迭代组成。在每次迭代中，具有比其任何未决定的邻居更高的密钥的未决定的节点应用Yao结构来约束度，决定剩余边缘上的主从关系，并通知所有邻居关于删除边缘或主从决策。据我们所知，我们的计划是第一个计划，构建度有限（一个节点最多有7个奴隶）和连接的微微网在多跳网络，没有停车的任何节点。除了维护一跳邻居的准确位置信息之外，创建和维护还需要很小的开销。实验证实了良好的功能，除了他们的快速创建和简单的维护创建蓝牙网络。
We address the problem of localized scatternet formation for multihop Bluetooth-based personal area ad hoc networks. Nodes are assumed to know their positions and are able to establish connections with any of their neighboring nodes, located within their transmission radius, in the neighbor discovery phase. The next phase of the proposed formation algorithm is optional and can be applied to construct a sparse geometric structure in a localized manner. We propose here a new sparse planar structure, namely, partial Delaunay triangulation (PDT), which can be constructed locally and is denser than other known localized planar structures. In the next mandatory phase, the degree of each node is limited to seven by applying the Yao structure, and the master-slave relations in piconets are formed in created subgraphs. This phase consists of several iterations. In each iteration, undecided nodes with higher keys than any of their undecided neighbors apply the Yao structure to bound the degrees, decide master-slave relations on the remaining edges, and inform all neighbors about either deleting edges or master-slave decisions. To the best of our knowledge, our schemes are the first schemes that construct degree limited (a node has at most seven slaves) and connected piconets in multihop networks, without parking any node. The creation and maintenance require small overhead in addition to maintaining accurate location information for one-hop neighbors. The experiments confirm good functionality of created Bluetooth networks in addition to their fast creation and straightforward maintenance.