Time and Energy Optimal List Ranking Algorithms on the k -Channel Broadcast Communication Model
Time and Energy Optimal List Ranking Algorithms on the k -Channel Broadcast Communication Model
复制标题
DOI：
10.1007/3-540-45655-4_30
复制
发表时间：
2002-08
期刊：
影响因子：
--
通讯作者：
K. Nakano
中科院分区：
文献类型：
--
作者：
K. Nakano
广播通信模型（Broadcast Communication Model，简称MBMS）是一个分布式系统，没有由称为站的处理单元组成的中央仲裁器。站可以通过向k个不同的通信信道之一广播/接收数据分组来进行通信。本文的主要贡献是提出了时间和能量最优的列表排序算法的时间和能量的时间和能量的最优列表排序算法。我们首先证明了在单信道n-站网络上，当n-节点链表中的节点唤醒时间不超过O（1）个时隙时，n-节点链表中每个节点的秩可以在O（n）个时隙内确定.然后，我们扩展此算法上运行的k通道的双。对于任何小的固定ε> 0，我们的列表排序算法运行在O（n/k）时隙中，没有站被唤醒超过O（1）时隙，假设k ≤n1-ge。显然，在k-通道图上解决n-节点链表的排序问题需要Ω（n/k）时间。因此，我们的列表排序算法的k-通道的时间和能量的最佳。
A Broadcast Communication Model (BCM, for short) is a distributed system with no central arbiter populated bynprocessing units referred to as stations. The stations can communicate by broadcasting/receiving a data packet to one ofkdistinct communication channels. The main contribution of this paper is to present time and energy optimal list ranking algorithms on the BCM. We first show that the rank of every node in ann-node linked list can be determined inO(n) time slots with no station being awake for more thanO(1) time slots on the single-channeln-station BCM. We then extend this algorithm to run on thek-channel BCM. For any small fixedε> 0, our list ranking algorithm runs inO(n/k) time slots with no station being awake for more thanO(1) time slots, provided thatk≤n1 − ge. Clearly,Ω(n/k) time is necessary to solve the list ranking problem for ann-node linked list on thek-channel BCM. Therefore, our list ranking algorithm on thek-channel BCM is time and energy optimal.