Worst-Case Nash Equilibria in Restricted Routing

We study the network routing problem with restricted and related links.There are parallel links with possibly different speeds,between a source and a sink.Also there are users,and each user has a traffic of some weight to assign to one of the links from a subset of all the links,named his/her allowable set.The users choosing the same link suffer the same delay,which is equal to the total weight assigned to that link over its speed.A state of the system is called a Nash equilibrium if no user can decrease his/her delay by unilaterally changing his/her link.To measure the performance degradation of the system due to the selfish behavior of all the users,Koutsoupias and Papadimitriou proposed the notion Price of Anarchy (denoted by PoA),which is the ratio of the maximum delay in the worst-case Nash equilibrium and in an optimal solution.The PoA for this restricted related model has been studied,and a linear lower bound was obtained.However in their bad instance,some users can only use extremely slow links.This is a little artificial and unlikely to appear in a real world.So in order to better understand this model,we introduce a parameter for the system,and prove a better Price of Anarchy in terms of the parameter.We also show an important application of our result in coordination mechanism design for task scheduling game.We propose a new coordination mechanism,Group-Makespan,for unrelated selfish task scheduling game with improved price of anarchy.     

无线传感器网络环境下基于事件 驱动应用的节能TDMA协议

媒质接入控制是无线传感器网络设计的关键问题之一.由于媒质接入控制协议直接控制着节点无线通信模块的活动,而无线通信模块是传感器节点能量消耗的主要来源,因此MAC协议节能效率的好坏将严重影响网络的性能.基于TDMA的MAC协议具有固有的节能特性,即通过合理的TDMA调度避免传输碰撞以及减少节点空闲监听的时间.本文提出了ED-TDMA协议,一种面向事件驱动的传感器网络应用的TDMA协议.该协议根据当前源节点的数目动态地改变TDMA帧的长度,提高了信道利用率;同时采用位图方式的TDMA调度,极大地减少了TDMA调度的开销,节约了能量.此外,通过引入簇内覆盖的思想,使得簇内的活动节点数目为一常数,同时减少了工作节点的数目,从而延长网络的生命周期,并在一定程度上提高了系统的可伸缩性.实验结果显示,ED-TDMA协议更适用于网络负载较低、节点密度高的无线传感器网络.     

SEEL:无线传感器网络下自适应、低延迟的节能媒质接入控制协议

无线传感器网络有着广泛的应用前景,然而由于传感器节点能量有限,因此传感器网络上运行的协议必须具备能量有效性以获得较长的生命周期.而媒质接入控制子层是节点能量消耗的主要所在,因此无线传感器网络设计的关键问题之一是媒质的接入控制.提出了一种自适应低延迟的节能MAC协议——SEEL协议,根据当前的网络负载自适应地调节竞争窗口的大小,从而减小节点数据传送的碰撞几率和由于碰撞而导致的能量消耗;采用了快速退避机制,减少了节点在退避过程中的空闲监听时间;扩展了RTS/CTS消息机制,可减少节点在每帧活动阶段的时间以及减小数据的延迟,两者都能节约能量的使用.实验结果显示,SEEL协议具有比S-MAC和TEEM协议更好的性能.