具有防共谋特征的占线网络设施选址机制研究

• 作 者: 程柏良[1]曾国荪[2]揭安全[3]
• 机 构: 同济大学电信学院计算机科学与技术系 上海 201804 江西师范大学计算机信息工程学院 南昌 330022
• 出 处: 第十七届全国网络与数据通信学术会议(NDCC2010)
• 发表日期: 2010年期

不同于离线网络,占线网络具有实时性和不可逆性。因此对于占线网络设施选址问题,一方面为了快速而有效地响应客户,需要立即确定客户是否可以获得来自设施提供的服务。另一方面一旦客户获得服务,客户与设施之间的服务链接不能再更改。在占线网络设施中,每个客户随机到达后,对服务进行投标,作为获得服务而愿意支付的最大成本。每个设施的开启均有一定的成本。因此需要通过机制设计来明确哪些设施为哪些客户提供服务,并明确获得服务的客户应承担的成本,使得网络总成本最小。客户出于自身利益最大化的考虑,会非真实披露购买服务的投标。更为严重的是网络中的多个客户可能通过共谋而以低成本获得服务,而对其他客户造成伤害。为此,本文通过交叉单调成本函数和组策略一致的概念,利用原始对偶思想,设计占线网络设施选址机制。在最坏/最好情况下以计算复杂性O(m*n3)/O(m*n2),获得3一占线近似预算平衡和防止共谋的目标。其中m是设施的数目,n是客户的数目。