The invulnerability characteristic of communication system is an important element in the study of military combat system. According to the organization structure and countermeasure of anti-air communication system, performance evaluation process algebra(PEPA) was introduced to describe the evolution process of anti-aircraft communication system by the state. PEPA-based invulnerability analysis method of communication system was proposed. A case study was given to testify the organization structure and the capacity against soft destruction or hard destruction of communication system by modeling and simulating. Experimental results show that PEPA is available for anti-aircraft communication systems' modeling and analyzing, which can realize the structural modeling in antagonistic process of anti-air communication system. The different elements of communication system have different influence on the invulnerability. Effective strategies can be taken to enhance the invulnerability of anti-aircraft communication system.