组合学在机械电子工程中的应用分析

摘　要：介绍了组合学在传感器网络节点布设中的应用。CMG机构的优化编码应用中，通过二维迷宫映射和其它数学建模步骤，将问题转化为图G（V，E）的k-顶点着色问题，并设计了CMG机构鉴别齿的编码及编码校验的组合学算法。传感器网络节点布设的应用中，重点介绍了传感器网络中覆盖问题的物理意义。

关键词：组合学；机械电子工程学；传感器网络
　　传统的机械工程可以分为制造和动力两大类。制造类包括毛坯制造、机械加工和装配三个生产过程;而动力类包括各种发动机。与自人类使用工具以来就有的机械工程相比，电子技术是二十世纪发展的新学科。机械工程与电子技术的结合始于上世纪。起初，二者结合是分离的“块与块”关系，或者是功能结构上的相互替代。随着计算机技术发展的推动，机械系统和电子系统通过信息有机地联系起来，形成了真正的机械电子工程。人工智能技术的发展与渗透，使得机械电子在传统的机械系统能量连接、功能连接的基础上，更加强调了信息连接和驱动，并逐步使机械电子系统向具有一定智能的方向发展。
一、组合学简介
　　组合学（Combinatorics）是研究离散结构的存在、计数、分析和优化等问题的科学。组合学源于数学娱乐和游戏，组合学问题在生活中随处可见，主要可划分为两类：排列的存在性、排列的计数和分类。组合学有两个研究领域：组合数学与组合学问题的算法。离散对象的处理是计算机科学的核心，研究离散对象的科学就是组合数学；程序就是算法，绝大多数情况下，程序算法是针对离散对象的，正是因为有了组合学问题的算法，才使人感受到计算机的“智能”。组合数学的主要研究内容有：鸽巢原理、排列与组合、二项式系数容斥原理及应用，递推关系和生成函数、特殊计数序列、二分图中的匹配、组合设计。组合学问题的算法，计算对象是离散的、有限的数学结构。
　　组合学问题的算法包括算法设计、算法分析两个方面。关于算法设计，历史上已经总结出了若干带有普遍意义的方法和技术，包括动态规划、回溯法、分支限界法、分治法、贪婪法等，应用相当广泛，如：旅行商问题、整数规划问题等。
　　组合学不仅是计算机科学的基础，在其它科学技术领域也有重要的应用。美国Sandia国家实验室有一个专门研究组合数学和计算机科学的机构，主要从事组合编码理论和密码学的研究，在美国及国际学术界都有很高的地位。
二、机械电子
　　早期的机械工业以手工加工为主，生产力低，但适应性强;三十年代开始集中在标准件和流水线，适合于大批量生产，但缺乏灵活性;现代生产一般要求转产周期短、生产灵活性强、产品质量高，因此常采用以机械电子系统为主要构成的FMS可以达到上述要求。与传统的机械工业相比，机械电子工程有着鲜明的特点:就设计而言，机械电子工程并不是一门有严格界线并且独立的工程学科，而是在设计过程中一个综合思想的实践。设计中，根据系统结构配置和目标，机械电子工程把它的核心部分(机械工程、电子工程、汁算机技术)与其它领域的技术，如:制造技术、管理技术和生产加工实践等有机地结合在一起，采用一种基于信息的自顶向下的模块化策略，完成设计就系统(产品)而言，机械电子系统(产品)结构简单，元件和运动部件少(如电子表)，它用小巧的电子系统取代“傻、大、笨、粗”的机械系统，减小了系统的体积，提高了性能，但是系统的复杂性却大大增加了。
　　机械电子学要求机械与电子技术的规划应用和有效结合，以构成一个最优的产品或系统。现代的机械电子系统除了“块与块”之间的动力联系之外，还有信息之间的相互联系，并由具有数值运算和逻辑推理能力的计算机来对机械电子系统的所有信息进行智能处理，人们已经认识到生产改革的未来属于那些懂得怎样去优化机械和电子系统之间联系的人;尤其是在先进生产和制造系统的应用中，对优化的需求将会变得更为迫切;在这些系统中，人工智能、专家系统、智能机器人以及先进的工艺制造系统将构成未来工厂的下一代工具。
三、CMG机构的优化编码
　　CMG机构是一种可用于引信保险与解除保险控制的密码鉴别机构。根据密码鉴别的功能要求及指定的“解锁符号序列”，设计CMG机构中复合齿轮A,B上鉴别齿(discrimination teeth)的二值装定编码，可称为“CMG机构编码”问题；基于工程优化的考虑，还希望编码得到的复合齿轮A,B，其齿轮层数N最小，此即CMG机构的优化编码问题。
　　为了解决CMG机构的优化编码问题，我们首先研究其数学建模的方法。在CMG机构编码类型划分的基础上[7]，基于“二维迷宫映射方法”[2]、迷宫映射图中“路格点(route grid)”和“阱格点(trap grid)”的概念[6]、及“关键陷阱格点(Critical Trap Grid，CTG)”互斥的“十字叉”判据[8]，将CMG机构的优化编码问题转化为无环、无重边的无向简单图G(V,E)的k-顶点着色问题(k-vertex coloring problem)。但k-顶点着色是组合学中著名的NP完全问题，穷举法的时间复杂度高达O(mn)(m表示染色数，n表示顶点数)。文献[9]已证明，对于任意CMG机构，密码齿轮层数至少为3；因此，即便在最佳情况下，穷举计算求解的时间复杂度也高达324。文献[10]提出了一种“基于团划分数的聚类算法”，对于任意一组指定的、有限长度的“解锁符号序列”，理论上可以求解得到所有的CMG机构优化编码，但其本质上仍然是穷举法，计算的时间复杂度仍为O(mn)。权衡计算的时间复杂度与优化设计目标，我们采用贪婪法求解CMG机构编码的顶点着色问题，该方法具有时间复杂度低、易于编程的优点，在大多数情况下可以获得优化编码结果。
　　基于贪婪法，采用Visual Basic编写了CMG机构的编码及编码校验程序[11]，包括编码、校验两个功能，实现了只需输入“解锁符号序列”，即可自动绘制二维迷宫映射图，求解并绘制密码齿轮编码示意图，以TXT文件输出设计结果，验证鉴别齿编码与“解锁符号序列”是否“锁-钥匹配”的功能。
四、传感器网络节点布设
　　传感器网络（sensor networks）涉及传感器、微电子机械系统（Micro-Electromechanical System，MEMS）、现代网络和无线通信等多种技术，将客观世界的物理信息与传输网络联系在一起，扩展了人们获取信息的能力，可应用在军事国防、工农业控制、城市管理、环境监测、抢险救灾、防恐反恐、危险区域远程控制等诸多领域，是当前IT 技术研究的热点。传感器网络的研究涉及通信协议、支撑技术、应用技术三部分，其中一个基本的问题是传感器网络节点的覆盖与连通。
　　传感器网络的每个传感器节点都能够采集、存储和处理环境信息，并与相邻的传感器节点通信。传感器节点的覆盖问题（Coverage Problems），就是要判断敏感区域被传感器监控或追踪的优良程度。例如，对于如图1所示的一个单位矩形敏感区域，假设采用5个同构的传感器如图布设，在完全覆盖该敏感区域的前提下，出于传感器节能设计的考虑，需要计算传感器的最小覆盖圆半径。这一问题在组合学中，可以用1-等圆覆盖问题 （1-Unit-Disk Coverage Problem）描述。




图1单位矩形敏感区域的1-等圆最优覆盖例（5圆覆盖，圆半径约为0.3621605）
　　为了定位需重点监测“热点（hot spots）”，跟踪活动目标的位置，或者为了提高传感器网络的容错能力（可靠性），需要考虑敏感区域的k-等圆覆盖问题。传感器节点k-等圆覆盖问题的物理意义是：设一组同构的传感器布设在某一区域，该区域中的任意一点应至少被k个传感器覆盖。事实上，传感器网络中可采用多种多样的异构传感器节点，由于各种传感器的敏感距离可以不同，因此，需要采用k-不等圆覆盖问题（k-Non-Unit-Disc Coverage Problem）描述二维区域的覆盖问题。
　　更进一步，传感器网络节点是在三维空间中布设的，假如每个传感器的敏感区域可用一个三维球体来模拟，则引出了传感器节点的三维空间覆盖问题。如果再考虑为了节能而规划传感器的值班时间、传感器节点发现目标的时延等，则情况更加复杂。
五、结论
　　组合学在诸多科学技术领域中有着重要应用价值。本文结合作者的研究工作，介绍了组合学在机械电子工程学领域的两个应用实例。
（1）CMG机构的编码问题，是设计一种微小型机械密码锁的关键。受微执行器（微电机）驱动能力的限制，并且为了提高密码锁装置的可制造性和可靠性，还希望CMG机构中复合齿轮A，B的齿轮层数N最小，此即CMG机构的优化编码问题。为了解决这一问题，我们通过“二维迷宫映射”和其它数学建模步骤，将问题转化为图G（V，E）的k-顶点着色问题，并设计了CMG机构鉴别齿优化编码、校验的组合学算法；
（2）传感器网络是传感器技术与网络通信技术相结合的产物，传感器网络节点的覆盖与连通是传感器网络规划的一个基础问题。

参考文献：
.~yctseng/Wireless Net05-02 /,2005-05.