Randomized initialization protocols for packet radio networks
Randomized initialization protocols for packet radio networks
复制标题
分组无线网络的随机初始化协议
DOI：
10.1109/ipps.1999.760530
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
S. Olariu
中科院分区：
文献类型：
--
作者：
Tatsuya Hayashi;K. Nakano;S. Olariu
本文的主要贡献是提出了一种有效的分组无线网络随机化的领导者选举和初始化协议。作为初始化协议的结果，PRN的n个站被分配从1到n的不同整数ID。结果包括协议：（1）初始化具有冲突检测（CD）能力的单信道PRN在O（n）轮中以至少1-1的概率/（2）在O（n/k）轮中以至少1-1/n的概率初始化具有CD能力的k通道PRN，每当k/spl les/n/3 log n;（3）以至少1 -1/n的概率在O（（log n）/sup 2/）个广播轮中在无CD的单通道PRN上选出领导者;（4）以至少1- 1/n的概率在O（n）个轮中初始化无CD的单通道PRN。（2/spl radic/n）;（5）在O（n/k）个广播轮中以至少1-1/n的概率初始化k信道PRN，其中没有CD，每当k/spl les/n/（4（log n）/sup 2/）。
The main contribution of this work is to propose efficient randomized leader election and initialization protocols for Packet Radio Networks (PRN, for short). As a result of the initialization protocol, the n stations of a PRN are assigned distinct integer IDs from 1 to n. The results include protocols to: (1) initialize the single-channel PRN with the collision detection (CD) capability in O(n) rounds with probability at least 1-1/(2/sup n/); (2) initialize the k-channel PRN with CD capability in O(n/k) rounds with probability at least 1-1/n, whenever k/spl les/n/3 log n; (3) elect a leader on the single-channel PRN with no CD in O((log n)/sup 2/) broadcast rounds with probability at least 1-1/n; (4) initialize the single-channel PRN with no CD in O(n) rounds with probability at least 1-1/(2/spl radic/n); (5) initialize the k-channel PRN with no CD in O(n/k) broadcast rounds with probability at least 1-1/n, whenever k/spl les/n/(4(log n)/sup 2/).