Morphological tree model for communication
protocol (example)
M.Sh. Levin
Sen. Res. Scientist, PhD
Inst. for Information Transmission Problems, Moscow
V.A. Ryabov
Student,
University of Toronto
1.
Introduction
In
recent years the significance of protocols for wireless communication systems
is increased (e.g., [1],[3],[4],[7],[8],[16],[17],[18],[19],[20]). The paper addresses
the usage of hierarchical model as “morphological tree” for communication
protocol family 802.11 (e.g., 802.11a, 802.11b, 802.11g) ([4],[16],[17],[19]). "Morphological tree" is a special
kind of “AND/OR tree” while taking into account compatibility (IC) of design
alternatives (DAs) for system parts/components ([10],[11],[13]). It is suggested to represent a
structural multi-version description for communication protocol systems and to
examine protocol design/analysis problems (hierarchical system design, evaluation/analysis of a composite system,
redesign (upgrade), design of a system trajectory, analysis of system
evolution, system forecasting). Examples briefly illustrate proposed
hierarchical modeling. Assessment of DAs and their compatibility is
based on expert judgment.
2. Morphological tree system model and design problems
In structured system modeling ([2],[5],[6]),
tree-like systems models have been widely used, for example: (1) tree, (2)
“holographic tree” [5], and (3) “And/OR tree” [6]. Here "morphological
tree" is examined (our system model where for each leaf node there is a
set of design alternatives DAs, this model is close to “AND/OR tree”
([10],[11]). Fig. 1 illustrates the "morphological tree" system model
and hierarchical morphological design. "Morphological tree" model
involves the following:
(1) tree-like system model,
(2) generated design alternatives DAs for each
leaf node,
(3) ordinal priorities for each DAs,
(4) ordinal estimates of pair compatibility
(IC) for DAs in each composite system node/branch (in Fig. 1: for nodes A, B,
C, and S), here pair of DAs are examined when elements of the pair are
correspond to different nodes (0 corresponds to incompatibility, 1corresponds
to compatibility at an initial level of quality, 2 corresponds to compatibility
at a more good level of quality, etc.).
The "morphological tree" system model
is a basis for a set of combinatorial technological problems (hierarchical
system design, evaluation/analysis of a composite system, redesign (upgrade),
design of a system trajectory, analysis of system evolution, system
forecasting) ([10],[11],[13]).
3. Basic design problems for protocol system
Our “morphological tree” model of a
communication protocol family can be used for several design/analysis problems
for protocol systems: (1) design/synthesis of a protocol for certain
application (e.g., manufacturing system, corporative application, research
institution, university, communication system as “bridge”), (2) revelation of
bottlenecks in existing protocols and their improvement/redesign, (3)
forecasting. Note real world communication systems (e.g., wireless sensor
networks [20]) can consist of various layers/subsystems/parts. In this case the
protocol selection/design problems can be considered as the design of a certain
protocol for each system part while taking into account the compatibility of
the selected/designed protocols for different system parts. A special
prospective research direction consists in the adaptation of an applied
protocol system, e.g., in on-line mode.
4. Hierarchical model and applied design examples
4.1 System structure
Here the following hierarchical structure is examined (Fig. 2):
0. Communication standard IEEE 802.11
S = B*C*D*E
1. Countries B:
Russia B1, USA B2.
2. Physical layer
C=H*F*G.
2.1 Methods for signal
modulation H = I*J*P*K:
1.1.1 FHSS I: modulation of the 2nd level I1, modulation of the 4th
level I2.
1.1.2 DSSS J: differential binary PSK J1, differential quadratic PSK J2,
CCK 5.5 Mbps J3, CCK
11 Mbps J4.
1.1.3 OFDM P: P1.
1.1.4 IR K: partitioning the flow into tetrads K1, partitioning the flow into bit
pairs K2.
1.2. Operational
spectrum F: 2.4…2.483 GGz
F1, 5.15…5.35, 5.725…5.825
F2.
1.3. Maximal
capacity G: 1 Mbps
G1, 2 Mbps G2,
5.5 Mbps G3, 6 Mbps G4, 9 Mbps G5, 11 Mbps G6(1), 12 Mbps G7, 18 Mbps G8, 24 Mbps G9, 36 Mbps G10, 48 Mbps G11, 54 Mbps
G12.
3. Channel layer D = L*O*R*X*M:
3.1. Network node L: DCF, CSMA/CA L1, PCF L2.
3.2. RTS/CTS O:
On O1, Off O2.
3.3. Security R = Q*Z*U*T:
3.3.1 SSID Q: On
Q1, Off Q2.
3.3.2 Encoding Z: WEP-64
bit key Z1, WEP-128 bit key Z2, WEP-256 bit key Z3, TKIP Z4,
AES Z5, MIC Z6, out of service Z7.
3.3.3 MAC address filtering U: On U1, Off U2.
3.3.4 Authentication T:
out of service T1, separated key
T2, WPA-PSK T3.
3.4. Testing the channel
by free usage X:
CCA X1, testing of carrier frequency X2.
3.5. Power consumption M:
mode of long-time usage M1, power saving demand mode M2.
4. Standard devices E:
PCMCIA cards for notebooks E1, PCI cards for PC E2, USB adapters
E3, chips for mother
boards E4, PDA chips for phones E5, access points
E6.
4.2 Criteria
A set of criteria for
assessment of DAs involves basic requirements to communication systems, for
example: (1) capacity, (2) quality of dataflow transmission, (3) quality of
transmission of large data packages, (4) power saving demands, (5) presence of
noise in channel (as a possible distance), (6) quality of collision detection,
(7) quality of collision resolving, and (8) reliability. An extended generalized
set of requirements to communication systems is described in [9]. Basic
requirements to communication protocols (e.g., for IEEE 802.11) is contained in
(e.g., [4],[16],[17],[19]).
4.3 Compatibility
Table 1 represents estimates for some DAs pairs: 3 corresponds to the
best compatibility, 2 corresponds to good compatibility, 1 corresponds to
possible compatibility, and 0 corresponds to impossible compatibility (expert
judgment, an example of compatibility estimates).
Table 1
Example for estimates of compatibility
|
DAs |
G1 |
G2 |
G3 |
G4 |
G5 |
G6 |
G7 |
G8 |
G9 |
G10 |
G11 |
G12 |
F1 |
F2 |
|
B1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
3 |
0 |
|
B2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
3 |
3 |
|
I1 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
I2 |
0 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
2 |
1 |
1 |
|
J1 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
J2 |
0 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
J3 |
0 |
0 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
1 |
1 |
|
J4 |
0 |
0 |
0 |
|
0 |
3 |
0 |
0 |
0 |
0 |
1 |
2 |
1 |
1 |
|
P1 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
1 |
1 |
|
K1 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
1 |
1 |
|
K2 |
0 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
1 |
1 |
4.4 Examples of composite solutions
Let us point out several examples of composite solutions for some
typical applications (here component E
is not considered):
(a) manufacturing
system: S1 = B1*I1*J4*P1*K1*F1*G12*L2*O1*Q2*Z5*U1*T3*X2*M2;
(b) corporative appication (offices):
S2 = B1* I1*J4*P1*K1*F1*G12*L2*O2*Q2*Z5*U1*T3*X1*M2;
(c) research institution: S3
= = B1* I1*J4*P1*K1*F1*G12*L2*O1*Q2*Z5*U1*T3*X2*M1;
and
(d) communication
system like “bridge”: S4 = = B1* I1*J4*P1*K1*F1*G12*L2*O2*Q2*Z5*U1*T3*X2*M1.
The above-mentioned solutions are based on engineering approach (expert
judgment). Evidently, here optimization approaches can be used for
combinatorial synthesis of the composite solutions, e.g., hierarchical
morphological multicriteria design (HMMD) approach ([10],[11],[13]).
5. Conclusion
The paper describes hierarchical model as “morphological tree” for
communication protocol family IEEE 802.11. In the main, several contemporary
versions of protocol IEEE 802.11 have been examined (e.g., 802.11a, 802.11b,
802.11g). Clearly, in this field new information is appeared permanently and new
versions of protocol 802.11 will require a modification of the considered
hierarchical model. At the same time, our suggested approach is a good basis to
represent a structural multi-version description for communication protocol
systems and to examine problems of their analysis, evaluation, design of a
version for a certain application, and forecasting. On the other hand, our
approach can be very useful for educational processes. The material is a
preliminary one. It is reasonable to consider other applications, other kinds
of models including taking into account uncertainty (e.g., [10]). Another
approach of communication protocol analysis is targeted to clustering of
protocol versions [14]. The draft material for the article was prepared within
framework of faculty course "Design of systems: structural approach",
Moscow Institute of Physics and Technology, Faculty of Radio Engineering and
Cybernetics (creator and lecturer: M.Sh. Levin) [12]. The above-mentioned
course was partially supported by NetCracker, Inc. [15].
6. References
2. R.C. Conant,
Information flows in hierarchical systems, Int. J. of General Syst., 1(1),
9-18, 1974.
3. D.J. Cook, S.K.
Das, (Eds.), Smart Environments: Technologies, Protocols, and Applications.
Wiley, 2004.
4. T. Cooklev,
Wireless Communication Standards: A Study of IEEE 802.11, 802.15, and 802.16.
IEEE Press, 2004.
5. Y.Y. Haimes,
Hierarchical holographic modeling, IEEE Trans. SMC, 11(9), 606-617, 1981.
6. D. Harel, And/Or
programs: a new approach to structured programming, ACM Trans. on Programming
Languages and Systems, 2(1), 1-17, 1980.
7. M.S. Gast, 802.11
Wireless Networks: Definitife Guide. O.Railly & Accosiates, 2002.
8. H. Karl, A. Willig,
Protocols and Architecture for Wireless Sensor Networks. Wiley, 2007.
9. N.A. Kuznetsov,
M.Sh. Levin, V.M. Vishnevsky, Some combinatorial optimization schemes for
multi-layer network topology. Electronic Proc. of the 17th IMACS World
Congress, paper T4-I-42-0486, Paris, France, July 2005.
10. M.Sh. Levin.
Combinatorial Engineering of Decomposable Systems, Kluwer, 1998.
11. M.Sh. Levin,
Composite Systems Decisions, Springer, 2006.
12. M.Sh. Levin, Course
"Design of systems: structural approach", DETC2006-99547, 18th Int.
Conf. on Design Theory and Methodology DTM, Pennsylvania, USA, Sept. 2006.
13. M.Sh. Levin,
Combinatorial technological systems problems (examples for communication
system). Intl. Conf. on Systems Engineering and Modeling ICSEM-2007, 24-32,
March 20-23, Israel, 2007.
14. M.Sh. Levin,
Towards hierarchical clustering, In: V. Diekert, M. Volkov, A. Voronkov,
(Eds.), CSR 2007, LNCS 4649, Springer, 205-215, 2007
15. Netcracker,
Inc. http://www.netcracker.com
16. B. O'Hara, A.
Petrick, The IEEE 802.11 Handbook: A Designer's Companion. 2nd ed., IEEE Press,
2005.
17. R. Olexa,
Implementing 802.11, 802.16, 802.20 Wireless Networks: Planning,
Troubleshooting, and Operations. Butterworth-Heinemann, 2004.
18. K. Sohraby, D.
Minoli, T. Znati, Wireless Sensor Networks: Technology, Protocols, and
Applications. Wiley, 2007.
19. B.H. Walke, S.
Mangold, L. Berleman, IEEE 802 Wireless Systems: Protocols, Multi-Hop
Mesh/Relaying, Performance and Spectrum Coexistence. Wiley, 2007.
20. V. Zadorozhny, P.
Chrysanthis, P. Krishnamurthy, Network-Aware Wireless Sensor Management.
Springer, 2007.