无线自组织网络中基于付费的路由和转发方法

摘要

无线自组织网络中基于付费的路由和转发方法是利用经济学中的VCG机制、Vickrey拍卖等方式，使真实地显示参与网络功能地开销成为Ad hoc节点最优的策略，在节点真实地显示其参与路由和转发分组的费用基础上，选择出费用最优的路径；在分组转发过程中，显式地考虑了最优路径上每个节点转发分组时不同的费用，所设计的对节点的补偿方案，能够防止节点的各种欺骗行为。该方法较好地解决了Ad hoc网络中，节点路由和转发机制中的激励问题，简化了节点的决策空间，防止了节点的各种“机会主义的”行为，实现了全局的目标最优，是较系统的基于经济模式的Ad hoc网络中激励问题解决方案。

主权项

1、一种无线自组织网络中基于付费的路由和转发方法，其特征在于在路由机制中，首先每个节点自己宣称参加网络功能的费用，设计对每个节点参加网络功能的补偿并做为每个节点参加网络功能的费用；使直接显示确定的参加网络功能的费用成为每个节点的最优策略；基于在路由阶段确定的每个参与节点的费用情况，构造了对最后一个转发节点的补偿值，以鼓励节点转发分组；确定对发送节点的补偿值，以防止节点勾结；最后设计每个转发节点的折扣率，以防止节点伪造收条，获取额外利益；该方法包括下列两方面的方法：A、路由方法：基于“Vickrey-Groove-Clark”机制的最小费用路径选择：采用机制设计中的VGC方案，计算对参与路由的节点的补偿，以激励用户真实地显示参与网络功能所招致的费用，并基于真实费用选择费用最优的路径；基于“Vickrey”拍卖的最小费用路径选择：采用目的地驱动的Vickrey拍卖机制，激励节点在路由机制中真实的竞标，并实现费用最优的路径的选择；基于方向辅助的Vickrey拍卖机制：在Vickrey拍卖过程中，采用方向辅助技术，减少获取费用较优路径时的开销；B、转发方法：目标是阻止节点的欺骗行为，并为节点提供转发分组的动机，转发方法防止节点的以下欺骗行为：当收到消息后，节点保存了收条，但没有转发分组；节点收到了分组，但没有报告收条；节点没有收到消息，但虚假的宣称他们收到了消息；所述的步骤A进一步包括下列具体方法：A1：按照最短路径算法，求出的从源S到目的D的费用最短路径为S，1，…n，D，按照VGC机制，对位于最短路径上的节点i的补偿为：α_i：＝|SP^-(i，i+1)|-|SP/(i，i+1)|，其中|SP^-(i，i+1)|表示缺少链路(i，i+1)时的最小费用路径，|SP/(i，i+1)|表示链路(i，i+1)转发费用为0时的最小费用路径；A2：基于Vickrey拍卖的最小费用路径选择，从目的节点开始执行Vickrey拍卖过程，纪录下获胜节点的集合，以及在此阶段对获胜节点所做的补偿；由获胜节点作为拍卖人继续相应的拍卖过程，并将上一轮拍卖人付出的代价加到新一轮获胜的竞标者上，作为新的获胜者的代价，并将新的获胜者加到获胜者集合中，由获胜者集合中的节点举行新一轮的拍卖，直到到达源节点；A3：采用所述方向辅助的技术，在从目的节点到源节点方向上，目的节点在本地举行拍卖，而对获胜节点的补偿是所有竞标的节点中次最低的竞标值，由获胜节点在接近于源节点方向上的邻居节点中迭代，进行上述的拍卖，直到到达源节点；所述的步骤B进一步包括下列具体方案：B1：按照上面A部分的基于付费的路由机制，确定从源S到目的D的费用最优路径p＝(n₀，n₁，…，n_k，…，n_d)，计算对节点n₁，…，n_k，…，n_d-1的补偿，分别表示为α₁，…，α_k，…，α_d-1，确定路径p上提交有效收条的最后一个节点k；B2：在分组转发时，对路径p上节点i转发分组的补偿值r_i；其中，折扣率γ＜1B3；计算对源节点S收取的费用：(α₁+…+α_d-1+β)-(d-k)γβ，估算节点相互勾结，使没有收到消息的节点也能伪造的收条的开销是δ。