数学模型在互联网通信中的应用研究.docx

2004 年 6 月第 26 卷 第 6 期系统工程与电子技术Systems Engineering and ElectronicsJun. 2004 Vol126 No16文章编号 :10012506X(2004) 0620829204数学模型在互联网通信中的应用研究苏光奎 , 李俊兵(武汉大学计算机学院 , 湖北 武汉 430072)摘 要 : 面对内外众多客户对 Web 服务信息的频繁访问请求 ,容易形成访问瓶颈 ,需有效合理地组织 、分配和 规划内部网 ( Intranet) 信息资源 ,以减轻服务器的负担 ;为避免过多地重复访问同一信息而浪费通信费用和增加信道 负担 ,必须设法降低访问费用 ,提高 Intranet 网的使用效率 。通过引入集合划分问题 ( set partitioning problem ,SPP) 和背 包问题 ( KNAPSACK) 的数学模型及相应算法 ,定量地解决了互联网通信中访问瓶颈和通信费用的问题 ,并为解决类 似问题开辟了一条新的途径 。关键词 : 数学模型 ; 访问瓶颈 ; 通信费用 ; 集合划分问题 ; 背包问题中图分类号 :U675. 65文献标识码 :AApplication of mathematical models in Internet communicationSU Guang2kui , LI Jun2bing( Computer Science College , Wuhan University , Wuhan 430072 China)Abstract : On account of the frequent information access from the users by the Intranet , the Web servers some2 times are overburdened. Consequently the access bottleneck occurs at times. It is necessary to organize and allocate the Intranet information resources properly on the Web servers. In order to avoid too many unnecessary accesses to the same extranet information resources from the Intranet , some ways should be found to reduce the communication cost andchannel burdens , and to enhance the efficiency of Intranet . Two problems are put forwand , i . e. access bottleneck and communication cost of Internet communications. And then two mathematical models and their algorithms set parti2 tioning problem( SPP) and KNAPSACK problem are introduced to construct the models of the two problems mentioned above , and solve these problems successfully. Moreover , a new idea is provided for solving the similar problem of dis2 tributed systems.Key words : mathematical model ; access bottleneck ; communication cost ; set partitioning problem; KNAPSACK1引言一个企业的专用网即 Intranet 网 ,在 Internet 上具有两种 功能 :对外 ,它要主动发布信息 ,介绍其最新产品和技术 ,在 公众面前为企业作宣传 ,以图丰厚的利润回报 ;对内 ,它自身 是一个 Internet 用户 ,必然要访问内部网以外的各种信息 ,以 便充分了解市场 。为在商业竞争中保持有利地位 ,面对如此 浩翰无垠的 Internet 信息和来自企业内外众多的访问请求 , 必须设法有效地组织和规划内部网的信息资源 ,以达到减轻 服务器负担 、降低访问费用 、提高 Intranet 网使用效率等目 的 。为了便于理解 ,可归纳成如下两个问题加以论述 。(1) 一般情况下 , 在企业内部分布信息时 , 总是在逻辑 上将相应的信息主题分成块结构 , 使内容彼此独立的信息 组成不同的信息块 。这些信息块分布在企业内部不同的 Web服务器上 。由于各信息块内容不同 , 其重要性及被感兴趣的 程度不同 , 因此它们被访问的频率也必然不同 。如果这些信 息块毫无规律地安置在各 Web 服务器上 , 必将使各个服务 器被访问的频率有显著差别 。最极端的情况则是其中的一 两台服务器被频繁访问 , 甚至有可能因负担过重而拥塞 , 而 其它服务器则显得“门前冷落”。一旦出现这种情况 , 最直接 的后果是资源浪费 , 此外 , 因为频繁地告诉用户“因访问者 太多 , 请您稍后再试”等信息 , 会使网上用户对此节点失去 耐心 , 从而失去某些无形资产 , 所以有必要对各信息块被访 问的频率进行统计 , 在此基础上建立数学模型 , 确定解决方 案 , 使各服务器所承受的负担尽可能均衡 , 防止造成访问 瓶颈 。(2) Intranet 用户必然同时也是 Internet 的用户 ,面对丰富 多彩的 Internet 信息资源 ,他们会频繁地访问 Internet 网络 。收稿日期 :2003 - 05 - 24 ; 修回日期 :2004 - 02 - 26 。作者简介 :苏光奎(1953 - ) ,男 ,教授 ,主要研究方向为智能接口 ,过程控制及通信。 830 系统工程与电子技术2004 年由于企业对 Internet 信息访问是有针对性的 ,有其明显的目 的 ,所以必然只对其中的一些信息资源感兴趣 ,访问也比较 频繁 ,从而使通信费用增长 。另一方面 ,有不同的用户会对 相同的信息主题产生兴趣 ,以至于屡屡击入相同的网址调用 这些信息 ,同样也会使通信费用增长 。为了有效地降低通信 费用 ,可以将那些被频繁访问的 Internet 信息下载至 Intranet 内部的 Web 服务器上 ,使之成为内部信息 , Intranet 用户可在 内部对其进行访问 。一旦成为内部信息 ,其通信费用和访问 速度就不可同日而语了 。所以也必须在统计的基础上 ,建立 数学模型 ,确定解决方案 ,切实有效地降低通信费用 ,提高访 问速度 。显然 ,上述两个问题是基于 Intranet 的分布式信息系统 信息组织和规划的关键问题 。前者是针对内部信息的组织素 之 和。 那 么 ,minimax2SPP 定 义 为 :minimize(max Ci ) ;maximin2SPP 定义为 maximize(min Ci ) 其中为 P 的任一划分。2. 2 LPT算法自本世纪以来 ,人们一直致力于构造一些好的性能保证 多项式时间近似算法 。本文采用其中最自然也是最有名的 LPT(longest processing time) 算法 。LPT 算法的思想叙述如下.(1) 把元素按单调递减顺序排列 , 不妨设 P1 P2 P3 Pn ,构成序列 L ;(2) 将 L 中的当前元素放入当前和最小的子集中 , 然后 从 L 中去掉它 。2. 3 性能比较记 = M1 , M2 , Mm 为由 LPT 得到的划分 , s+ = M+1 , M2 , M m 为相应问题的最优划分 , 并且分别记 Mj安放的 ,可概括为访问瓶颈问题 ;后者则是针对外部通信的 ,和 M+jjj 的元素和为 Cj 和 Cj ,令 M = max Cj , W = min Cj ; M =称为通信费用问题 。本文将就这两个问题分别提出其数学max C+ , W+= min C+ ;则有模型和求解方法 。2访问瓶颈问题的数学模型及求解对于 minimax2SPP M M+ 43- 1 3 m2. 1 数学模型首先对访问瓶颈问题作如下描述 :将一定数量的信息块 存放到规定数目的服务器上 ,由于各信息块被访问的次数不 同 ,存放的原则是使各服务器被访问的次数尽可能相等 。在对于 maximin2SPP W W+2. 4 推广到 NSPP3 m - 1 4 m - 2数学上 , 这是一个集 合 划 分 问 题 ( set partitioning problem , SPP) 。所谓集合划分问题 , 是指将一给定集合划分为指定个 数互不相交的子集 ,并使每个子集含有的元素大小之和尽可 能一致 。它的判定问题严格叙述为 : ( SPP) 实例 :有穷集合 A= a1 , a2 , , an ,以及每一个 a A 的“大小”w ( a) R+ ;正整数 m Z+ , 问 :是否存在一个关于 A 的划分 = A1 , A2 , , Am 使 得 j = 1 ,2 , , m , 有 W ( a) =a Aj 1 W ( a) ? m a A由此 , 访问瓶颈问题可以形式化地描述为 : 将一给定的 信息主题集合 A = a1 , a2 , an ( n 个信息主题) 划分为 m 个互不相交的子集 ( 即分配至 m 台服务器) , 并使每个子集 (服务器) 含有的元素大小 ( 受访问频率) 之和尽可能一致 。 在实际应用中 ,访问频率 w ( a) 可由统计软件来测量 。它具有 一定的稳定性 ,同时也因为各种因素影响 ( 如信息的老化 、经济因素 、政策政治因素等) 而呈现动态变化 ,因此 w ( a) 是一 个与时间等参数有关的函数 , 但 w ( a) 有一定的统计规律可在企业专用网内 ,因为每个部门均有自己的 Web 服务 器 。在一般情况下 ,与本部门有关的信息块将存放在该部门 的 Web 服务器上 ,以便于使用和管理 。也就是说 ,有可能会 指定某些信息块必须存放在确定的服务器上 。针对这种情 况 ,相应地 ,可将 SPP 进一步推广 ,这便是带核集划分问题 , 简称为 NSPP。在数学上 ,可将它描述如下 。有限集 A = p1 , p2 , pn g1 , g2 , gm , 其中 P= p1 , p2 , pn 是非核元集 , 称对应的信息主题为非核信 息主题集 。G = g1 , g2 , gm 为核元集 ,称对应信息主题为 核信息主题集 。它与 SPP 的区别在于在 A 的划分 = M1 , M2 , Mm 中 ,必须有 gj Mj+ j 对核元 gj ,要求 gj 非负 。 于是类似地得到两个问题 :maximin2NSPP 和 minimax2NSPP。当 LPT 应用它们时 ,首先放置 gj 于 Mj , 然后再按 LPT 放置非核 元 。这样的经过修正的称 LPT为 MLPT。同样 ,maximin2NSPP 和 minimax2NSPP 也有一个性能问题 。再次引用上一节中的标记 M , M+ , W , W+ ,则有对于 minimax2NSPP m3 1 循 , 在一定的时间段内是稳定的 。当采集到的 w ( a) 发生变化时 ,后面提及的算法可动态地调整对文件的分配 。 在数学上 , 称使各子集中元素大小之和尽可能一致的SPP 为 SPP 优化问题 。对于它 , 人们通常从两个方面来考 虑 。其一是使最大的子集最小化 (记为 minimax2SPP) , 另一是 使最小的子集最大化 (记为 maximin2SPP) 。下面给出其数学 描述 。以正数集 P = p1 , p2 , pn 代替 A ,其中 p 代表 pi 的大 小; P 划分成 = M1 , M2 , Mm 个子集 ,同时 Ci 代表 Mi 中元m+ 2 - 2 m对于 maximin2NSPP w 2 m - 1w+3 m - 2在数学上 ,算法的分析必须考虑到最坏情况 。但是 ,在 工程上这种极端的情况是很少出现的 。所以 , 引入 LPT 和 MLPT 算法就能有效地解决访问瓶颈问题 。可以利用工具软 件 ,首先对各带核和不带核的信息主题进行统计和分析 ,在 此基础上对各信息主题进行优化组合 ,使得各 Web 服务器信第 26 卷 第 6 期数学模型在互联网通信中的应用研究831 息量分布合理 ,负担均衡 ,并使资源合理配置 , 达到 Intranet稳定有效运行之目的 。3通信费用问题的数学模型及求解3. 1 数学模型首先将通信费用问题作如下描述 :现企业内部网中有一 节点专门用来存放从外部调入的信息 。因该节点容量有限 , 问怎样有目的地选择信息放入节点 ,在不超过最大容量的情 况下 ,使节点的使用效率最高 。在数学上 ,这是一个背包问题 ( KNAPSACK) ,背包问题的 数学描述如下 。设有一位旅行家 , 在出发前准备一只背包 , 限制背包内 物体的总重量不超过 b 。现有 n 类物体 p1 , p2 , , pn , pi 类中 每个物体的重量为 wi 价值为 vi ,1 i n ,物体不能拆开 。问 怎样把物体放入背包内 ,在不超重的条件下使背包内物体的 总价值最大 ?然后尽量挑选比值大的信息块先调入 a , 即按递减序列将各信 息块依次调入 a ,到最后可能还剩余部分容量小于按顺序该调 入 a 的信息块的容量。此时 ,依次比较其后的每一个信息块 ,直 到找到一个可放入的为止。若所有的信息块容量均大于剩余容 量 ,则前面调入 a 的信息块即为解。“贪婪算法”虽然很直观 ,但是它的解并不一定是最优 解 ,有时甚至与最优解相距甚远 ,误差超过可以忍受的范围 。 所以 ,在精度较高的场合下一般使用分枝定界算法 。该算法 对一切可能的状态逐个搜索比较将出现指数型的复杂性 。 因为本文主要是利用这种算法解决工程问题 ,所以必须综合 考虑精度和复杂性 ,在兼顾两方面因素的前提下 ,采用一种 近似算法 ,其算法主要的思想如下 。(1) 问题的解由向量 ( x1 , x2 , xn) 表示 , 取部分向量( x1 , x2 , , xk) 表示部分解 , k k ,使得 M - Si xi Si ,这表示在 ai = 1内还可以放入某个信息块而容量不至于超过 M ,则依次比较问题可归纳为下列数学问题 :目标函数 :max z = vi xi ; 约i = 1n束条件 : wi xi b , 求满足约束条件并使目标函数值最大i = 1的解 ( x1 , x2 , xn) 。由此 , 通信费用问题可以形式化地描述为 : 设在内部网 Intranet 之外有 n 个信息块 , 其信息量大小为 S , 对某个信息 块每调用一次的费用为 F ,这里考虑到信息的有偿服务附加 因素 ,假定对不同站点 、不同信息调用的费用也不相同 。本文最后 个下载信息块之后的量 , 直到找到一个放得下的信 息块为止 。若还有剩余容量 ,则作循环 , 直到所有的任何信息 块均比较完 ;k对于所有 j k , M - Si xi Si ,这说明在 a 内已不i = 1能放入任何一个信息块 ,否则会超过 M ,则 j k 时 , xi = 0 。 (2) 取部分向量 ( x1 , x2 , xk , xk+1) 表示部分解 , 转以 上步骤 ,其中 h 为小于 n 的整数 , IM 存放最佳结果的 I , 当 k提出的通信费用实际上是单纯的通信费用和信息服务费等 附加费用的总和 ,从而调用信息的通信费用与信息容量的大0 时 , k 个 元 素 的 子 集 数 目 为n nk ,kn= 1 ,0nkkk+1小不一定成正比 。费率因子 R = Fi/ Si 不为常数 ;还可以用统 nk = n - 1 = 0 ( nk) , 故近似算法的复杂性计软件获得每个信息量为 Si 的信息块在一定时间内的访问k = 0kk+1)k =0n - 1次数 Ti ,现在要选择部分信息单元调入内部网某一站点 a , a所允许的最大容量为 M 。则在信息内容不能全部调入的情况 下 ,问怎样把一些信息单元调入 a , 在不超过最大容量的情 况下 , a 内信息的实用价值最大 ?为 O ( n。3. 3 性能比较设通信费用算法的最优解为 Z+ ,上述算法的解为 Z 。可+以证明 : Z - Z 1 。0Zn + 1设 xi =,0 表示不调入内部网 ,1 表示调入内部网 。则1该算法的性能与 h 的取值有关 。当 h h+ 时 , Z = Z+ ,+通信费用问题可归纳为下列数学问题 : 目标函数 :max z =即近似算法得出的解是最优解 ;当 h h时 ,此时近似算法nn不能保证一定获得最优解 。vi xi ;约束条件 : Si xi M ,求满足约束条件并使目标函通过引入背包问题及其解法 ,成功地解决了通信费用问i = 1i = 1数值最大的解 ( x1 , x2 , xn) 。这里 , vi = Fi 3 Ti 表示所调入a 的信息 ,若费用越高访问次数越多 ,则实用价值越大 。3. 2 通信费用问题的算法在数学上 ,背包问题可以用很多算法求解 ,其中最直观的算 法是“贪婪算法”。它是依照一种最优度量法即每步都取局部最 优值最后求得解的过程。对应通信费用问题 ,其算法思想可以简单描述如下 :先把要调入内部网的各信息块按 vi 的比值排序 ,si比值高的信息块排在前面 , 比值较低的排在后面 , 呈递减序列。题 。它具有精度高 ,容易用程序实现等优点 , 对于企业内部网具有重要的实际意义 。4结束语分布式信息系统信息组织的优化问题包含诸多因素 。 本文分析并成功地解决了其中两个主要问题 。但事实并非 如此简单 ,随着企业内部网的发展和完善 ,有可能碰到以下 问题 :内部网的各个 Web 服务器容量太小 ,不能容纳与日俱 增的信息内容 。同时 ,各个 Web 服务器上每块信息的容量和832 系统工程与电子技术2004 年被访问次数都不相同 ,问如何将这些信息分布到不同的 Web 服务器上 ,在不超过各个服务器容量的情况下 ,使得每个服 务器被访问次数尽可能相等 ? 随着企业的不断发展 ,必然会 提出新的问题 ,新的问题需要新的方法来解决 。本文提出的 数学模型为企业信息规划奠定了解决各种问题的基础 ,并为 解决问题提供了有关思路 。参考文献 : 1 王能超. 数学模型方法 M . 武汉 :华中理工大学出版社 ,2001. 2 邱伟 ,郁松年. 组合数学 M . 北京 :国防工业出版社 ,2003. 3 陈义华. 数学模型 M . 重庆 :武汉大学出版社 ,2000. 4 Kushida T. An Empirical Study of the Characteristics of Internet Commu2 nicationJ . Computer Communications , 1999 : 160721618.(上接第 716 页)始频率 f1 = 0. 1 ,调频斜率 1 = 01000 8) 和信号 2 : s1 ( n) =e j2( f 2 n+ 2 n )法 。通过对阵元输出进行时频分析获得信号的瞬时频率特 性 ,并据此在信号时频脊点上构造方向向量和修正 STFD 矩122(初始频率 f2 = 0. 4 , 调频斜率 2 = - 01000 8)分别以 30和 35入射到 8 元均 匀直线阵列 。信噪比为 5 dB ,快 拍数 为 256 。阵 元 1 输 出 的 WVD 如图 4 所示 。从图中可 以看出信号频率的变化趋势 。 根据 WVD ,可以估计出信号的 频率参数 (对线性调频信号包 括信号在各时刻的瞬时频率和图 4 阵元 1 输出的 WVD (SNR = 5dB)阵 ,可把一般信号的阵列输出建模成与窄带阵列信号处理类似的模型 ,从而可以应用子空间算法 MUSIC 进行 DOA 估计 。 由于修正 STFD 矩阵是建立在信号的时频脊点上 ,因此 ,修正 STFD 矩阵具有信号选择性 ,如果选择恰当 ,可以使得每个修 正 STFD 矩阵对应一个信号源 ; 同时由于高斯噪声功率平均 分布在整个时频平面上 ,这也会使得信噪比提高 ,有利于提 高 DOA 估计性能 。仿真结果表明了分析的正确性和算法的 有效性 。信号的调频斜率) 。同理 ,在两信号的时频不交迭的时刻构 造两个修正 STFD 矩阵并求 MUSIC 空间谱 ,如图 5 所示 。(a) 信号 1 的 DOA 估计 ,(b) 信号 2 的 DOA 估计 ,估计的 DOA 为 29. 91,估计的 DOA 为 35. 09,实际 DOA 为 30实际 DOA 为 35 图 5 对两线性调频信号源的 DOA 估计作 100 次随机实验 , 对信号 1 估计的 DOA 在 29. 61,30. 24之间 ,均方根误差为 0. 107 3。对信号 2 估计的 DOA在 34. 94, 35. 19之间 ,均方根误差为 0. 057 7。6结论本 文提出了利