新一代互联网-第二章.ppt

博弈过程 在 中，若只有一个这样的 存在，则把其作为用户和网络提供方最佳策略对。若存在多个这样的 或不存在这样的 ，则进一步比较Pareto优势，选择与 最小值对应的策略对作为最佳策略对（若有多对，则任选其一） 基于人工鱼群的QoS单播路由机制 算法描述 算法目标 在满足用户QoS需求的前提下使双方效用在所选路径上达到或接近Nash均衡下的Pareto最优 (19) (20) (21) (22) (23) (24) (25) 基于人工鱼群的QoS单播路由机制 (26) (27) (28) (29) 基于人工鱼群的QoS单播路由机制 算法目标 算法描述 人工鱼群算法 模拟鱼群行为的群体智能方法 主要模拟鱼的觅食、聚群和追尾行为，通过人工鱼个体局部寻优，达到在人工鱼群中突现全局最优 基于人工鱼群的QoS单播路由机制 解的表达 人工鱼对应问题解即QoS单播路径 采用向量表示形式 组成路径的边按从源到目的地的方向依次作为向量元素 基于人工鱼群的QoS单播路由机制 解的表达 初始解生成 采用随机路径算法生成初始解 算法过程 步骤1：当前访问节点 ，上次访问节点 ，将 压栈；标记图中所有节点状态均为“未访问”。 步骤2：若 = ，则失败结束；若 ，则转步骤3，否则转步骤5。 基于人工鱼群的QoS单播路由机制 解的表达 初始解生成 采用随机路径算法生成初始解 算法过程 步骤3：置 状态为“已访问”。若 的所有相邻节点都处于“已访问”状态，则弹出栈顶元素给 ， ，转步骤2。 步骤4：从 的相邻节点中任选一处于“未访问”状态的节点 ；从 与 之间的边中任选一条作为从 到 路径的组成边；将 压栈， ，转步骤2。 步骤5：若路径满足式(22)－式(25)，则把其作为初始解，成功结束；否则，失败结束。 基于人工鱼群的QoS单播路由机制 解的表达 适值函数 代表人工鱼 适值越小，解越优 基于人工鱼群的QoS单播路由机制 (30) 人工鱼距离、行为及其选择 两条人工鱼 和 间的距离定义如下： 式(31)表示在与 和 对应的向量中有 对分量不相同 将 中这样的分量即边的集合记为 设 表示 的感知距离，则满足 的所有 构成 的邻域 表示人工鱼移动步长 表示拥挤度因子 (31) 基于人工鱼群的QoS单播路由机制 基于人工鱼群的QoS单播路由机制 人工鱼距离、行为及其选择 觅食行为 步骤1：设定 ， 步骤2：对 ，在其邻域内任选一 步骤3：若 ，则转步骤4，否则 向 方向移动一步：随机产生整数 ( )，若 ，则 ；在 中任选 条边进行变换，使其与 中的对应边相同，觅食行为结束 步骤4： 。若 ，则转步骤2；否则， 随机移动一步：随机产生整数 ( )，在 中任选 条边进行随机变换，觅食行为结束 人工鱼距离、行为及其选择 聚群行为 步骤1：确定 邻域内所有人工鱼组成的集合 步骤2：确定 的中心位置 ，其中，  是 中的人工鱼在第 个分量上使用最多的边（若有多条这样的边，则任选其一） 步骤3：若 ，则 向 方向移动一步，方法同觅食行为步骤3；否则，执行觅食行为。聚群行为结束 基于人工鱼群的QoS单播路由机制 人工鱼距离、行为及其选择 追尾行为 步骤1：从 中选出适值最小的 （若有多个，则任选其一），