Approximation for a scheduling problem with application in wireless networks

来源 :Science China(Mathematics) | 被引量 : 0次 | 上传用户:simba_m
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
A network of many sensors and a base station that are deployed over a region is considered.Each sensor has a transmission range,an interference range and a carrier sensing range,which are r,αr and βr,respectively.In this paper,we study the minimum latency conflict-aware many-to-one data aggregation scheduling problem:Given locations of sensors along with a base station,a subset of all sensors,and parameters r,α and β,to find a schedule in which the data of each sensor in the subset can be transmitted to the base station with no conflicts,such that the latency is minimized.We designe an algorithm based on maximal independent sets,which has a latency bound of(a+19b)R + Δb-a + 5 time slots,where a and b are two constant integers relying on α and β,Δ is the maximum degree of network topology,and R is the trivial lower bound of latency.Here Δ contributes to an additive factor instead of a multiplicative one,thus our algorithm is nearly a constant(a+19b)-ratio. A network of many sensors and a base station that are deployed over a region is considered. Each sensor has a transmission range, an interference range and a carrier sensing range, which are r, αr and βr, respectively. the minimum latency conflict-aware Given of sensors along with a base station, a subset of all sensors, and parameters r, α and β, to find a schedule in which the data of each sensor in the subset can be transmitted to the base station with no conflicts, such that the latency is minimized. We designe an algorithm based on maximal independent sets, which has a latency bound of (a + 19b) R + Δb-a + 5 time slots, where a and b are two constant integers relying on α and β, Δ is the maximum degree of network topology, and R is the trivial lower bound of latency. Here Δ contributes to an additive factor instead of a multiplicative one, thus our algorithm is nearly a constant (a + 19b) -ratio.
其他文献
在竞争日益激烈的今天,售后服务成为展开差异化竞争、实现超额利润的重要手段.为此,企业需要建立高效的售后服务体系,为客户提供优质的售后服务,例如产品维修、升级、配件销
会议
在装有助力器的自行车运动中,对13名被测试者的心肌活动和肌肉活动的客观指标(扭矩和速度等)测量分析的基础上,同时使用NASA-TLX方法测试了精神要求等6项主观指标的数据,并采
研究了属性权重信息完全未知且属性值以区间数形式给出的不确定型多属性决策问题,提出了一种基于区间数距离和理想方案的求解属性权重公式,并给出了一种基于可能度的决策方案
目前侵袭性真菌感染(invasive fungal infections, IFI)的诊断标准一直存在争议,为给IFI下一个标准化的定义,中国侵袭性真菌感染工作组经反复讨论,并参照欧洲癌症研究和治疗
本文根据酒店客房种类和顾客到达方式的差异分别建立不同的动态规划模型,并就具体模型的重要性质进行了细致的讨论和证明.不同于以往的文章,本文主要研究酒店在面临团队客户
毛霉菌病是由毛霉目真菌引起的一类条件致病性真菌病,可引起易感人群鼻、脑、胃肠道、皮肤等多部位的感染。近年来该病的发病率渐有升高之势,国内外对该病的研究也有了一些新
会议
目的:探讨农村正常婴幼儿肠道微生物菌群分布情况,为从饮食上调节婴幼儿肠道微生物菌群的正常分布提供实验基础,从而减少婴幼儿肠道疾病的发生,增进儿童健康.方法:采用分层随
肺孢子菌于1909年和1910年由Chagas和Carini在锥虫感染的豚鼠和大鼠肺组织中首先被发现,被认为是锥虫的一种类型。有学者将之与其他38种真菌的分子进化树进行比较,证实PC为真
会议
目的:分析艾滋病合并侵袭性真菌感染的发生情况及临床特点,为其诊治提供参考。 方法:回顾性分析85例艾滋病患者的临床资料,总结侵袭性真菌感染的发病情况及临床特点。 结
会议