# Accurate Localization in Wireless Sensor Networks in the Presence of Cross
Technology Interference

Usman Nazir
Department of Computer Science  Syed Babar Ali School of Science and
Engineering
Lahore University of Management Sciences (LUMS)  Lahore  Pakistan
<EMAIL_ADDRESS>
###### Abstract

Localization of mobile nodes in a wireless sensor networks (WSNs) is an active
area of research. In this paper, we present a novel RSSI based localization
algorithm for 802.15.4 (ZigBee) based WSNs. We propose and implement a novel
range based localization algorithm to minimize cross technology interference
operating in the same band. The goal is to minimize the mean square error of
the localization algorithm. Hardware implementation of the algorithm is in
agreement with ideal (no interference) simulation results where an accuracy of
less than 0.5m has been achieved.

###### Index Terms:

Wireless Sensor Network, Localization, 802.15.4, RSSI, Kalman Filter, ISM,
CTI, Range-Based Localization, ZigBee

##  I Introduction

TABLE I: Specifications of SYNAPSE RF266 Module Parameters |  Value
---|---
Indoor Range |  Up to 200ft. at 250kbps
Outdoor LOS Range |  Up to 4000ft. at 250kbps
Transmit Power Output |  20dBm
RF Data Rate |  250kbps, 500kbps, 1Mbps,2Mbps
Receiver Sensitivity |  -107 dBm
Supply Voltage |  2.7 - 3.6 V
Transmit Current (Typ) |  130 mA
Receive Current (Typ) |  25 mA
Sleep Current (Typ) |  1.18 $\mu$A (internel timer off) & 2.3 $\mu$A (internel timer on)
Topology |  Mesh (SNAP)
Number of Channels |  16

Physical location of mobile nodes is often required for a large number of
applications in wireless sensor networks (WSNs). Localization techniques can
be broadly classified into range free or range based, anchor free or anchor
based and distributed or centralized techniques. Centralized localization
techniques [1, 2, 3, 4, 5, 6] transfer the entire data to a centralized node,
where the localization algorithm estimates the position for all of the mobile
nodes. These techniques have a lot of communication overhead. In the
distributed localization techniques [1, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24, 6], the mobile nodes are themselves capable of
estimating their location. The location of the mobile node is transferred to
the central node only in case of an event or with the sink initiated query,
depending on the network design, thereby reducing the communication cost
significantly. Anchor free techniques [8, 3, 14, 15, 16, 17, 19, 21] do not
requires beacon signals from the anchor nodes but offer very limited
localization accuracy whereas anchor based techniques [1, 7, 9, 10, 2, 4, 5,
11, 12, 13, 18, 19, 20, 22, 23, 24, 6] require beacon signals from anchor
nodes of known location. Range free techniques [8, 9, 10, 2, 3, 4, 11, 13, 14,
15, 16, 17, 18] rely on attributes such as hop count, connectivity information
etc. Although, these are cost effective techniques but localization results
are not accurate. The Range based techniques [1, 7, 9, 5, 12, 19, 20, 21, 22,
23, 24, 6] rely on received signal strength indicator (RSSI), time of arrival
(ToA), angle of arrival (AoA), time difference of arrival (TDoA) etc. ToA, AoA
and TDoA, all have better localization accuracy as compared to RSSI based
techniques but require additional hardware for their implementation.

The RSSI based localization schemes are by far the most popular localization
techniques employed for monitoring location of mobile sensor nodes as it
requires minimal, low cost hardware for its implementation. In RSSI based
localization implementations, RF transceivers capable of measuring RSSI are
used for location estimation. Multiple technologies for instance IEEE 802.15.4
(ZigBee), IEEE 802.15.1 (Bluetooth) and IEEE 802.11 (WiFi) all share the same
2.4 GHz ISM band [25]. The interference caused by these technologies causes
RSSI to fluctuate rapidly, causing packet collisions and affecting the
localization accuracy. Addressing cross technology interference (CTI) is
therefore critical for systems operating in license free ISM bands. The
highest CTI for a Zigbee based radio is caused by Wifi signals, because Wifi
is often co-located with IEEE 802.15.4 networks.

In order to minimize RF interference at the receiver front end, we use
aggregation function to calculate average RSSI values. We have used Synapse
RF266 sensor nodes having 802.15.4 radios and specifications shown in Table I.
Detailed specifications can be seen in [26]. ZigBee and WiFi radio channels
are shown in Fig. 1. As shown, the bandwidth of each ZigBee and Wifi channel
is 2MHz and 22MHz respectively, whereas separation between two adjacent ZigBee
and Wifi Channels is 5MHz [27]. In Wifi band, non overlapping channels are
used in Europe and North America [28]. Typically, channels with high
interference have higher mean RSSI values [29]. Therefore, ZigBee channel with
the lowest average RSSI value is selected to acquire minimal RF interference
with Wifi signals [29]. In addition to RF interference, the received signal
also gets affected by White Gaussian noise at the receiver front end which has
an infinite spectrum and thus infinite energy. To cater this problem, we
introduce Kalman filtering at the receiver front end. We show that if RSSI
after being processed for interference minimization and noise filtering is
given as an input to a trilateration localization algorithm, mean square error
of the localization algorithm is minimized.

The main contributions of this paper have been summarized as follows:

  * •

We introduce a novel cross technology interference minimization scheme with
trilateration for an improved accuracy.

  * •

We propose the use of Kalman filter at the receiver front for noise
minimization of localization algorithms.

  * •

Hardware implementation of the localization algorithm with minimal CTI and
noise reduction.

The remainder of the paper is organized as follows. Section II explains RSSI
based localization algorithm along with CTI minimization and noise reduction
techniques. Complete system design with hardware implementation has been
presented in Section III. Discussion on experimental results has been
elaborated in Section IV. Node deployment strategy is discussed in section V
and Section VI outlines the future directions and concludes this paper.

Figure 1: ZigBee and WiFi RF channels in 2.4 GHz band. ZigBee channel is 2 MHz
wide and WiFi channel is 22 MHz wide

##  II Proposed Localization Algorithm with Kalman Filtering

As discussed in Section I, localization algorithms can be classified in the
following ways:

  1. 1.

Centralized or Distributed Algorithms

  2. 2.

Range free or Range based Algorithms

  3. 3.

Anchor free or Anchor based Algorithms

Each type of localization technique has its advantages or disadvantages. A
detailed discussion on the merits and demerits of localization techniques is
out of scope of this paper, however a summary of the state of the art for
localization algorithms has been provided in Table II. In this paper we make
use of a distributed, range and anchor based localization algorithm to
localize a target (mobile) node.

###  II-A Log Distance Path Loss Model

The algorithm runs on the mobile node where RSSI of neighboring nodes is
needed. In our algorithm we use aggregation function, which averages the
received RSSI over multiple acquisitions, to verify the the RF interference
between ZigBee and Wifi Channels. The ZigBee channel with lowest mean RSSI
Value gets selected for communication. RSSI values of neighboring nodes are
acquired at the mobile node over the selected frequency (channel). The mobile
node then makes use of the log distance path loss model, given below in
equation 1, to calculate its distance to the neighboring transmitting nodes.

$RSSI{(d)}=RSSI{(d_{o})}-10n\times log{(d/d_{o})}$ (1)

where $d$ is the distance between transmitter and the receiver, $d_{0}$ is a
reference distance which we is assumed to be 1 meter. $RSSI{(d_{0})}$ is the
RSSI at reference distance taken as -45dBm and $RSSI{(d)}$ is the received
signal strength at distance $d$. Since a Trilateration approach [30] has been
used to estimate the location of sensor node, RSSI value for at least three
neighboring nodes is required for a valid location estimate of the mobile
node. Once the location estimate from trilateration algorithm is received, a
Kalman Filter is used to minimize the mean squared error. A flow chart of the
the localization process has been presented in the Fig. 2.

Figure 2: Proposed Localization Algorithm

###  II-B Trilateration

In a trilateration algorithm along with the minimum mean square estimation
(MMSE) [30] [31], the position of the mobile node can be computed by solving
the following equation:

$\hat{P}=\left(\\!\begin{array}[]{c}\hat{x}\\\
\hat{y}\end{array}\\!\right)=(A^{T}A)^{-1}A^{T}B$ (2)

where $\hat{P}=(\hat{x},\hat{y})^{T}$ denotes the estimated target location,
and the matrices A and B are defined as

$A=\left(\IEEEeqnarraybox*[][c]{,c/c,}2(x_{2}-x_{1})&2(y_{2}-y_{1})\\\
2(x_{3}-x_{1})2(y_{3}-y_{1})\right)$ (3)
$B=\left(\IEEEeqnarraybox*[][c]{,c/c,}d_{1,target}^{2}-d_{2,target}+(x_{2}^{2}+y_{2}^{2}-x_{1}^{2}-y_{1}^{2})\\\
d_{1,target}^{2}-d_{3,target}+(x_{3}^{2}+y_{3}^{2}-x_{1}^{2}-y_{1}^{2})\right)$
(4)

where $(x_{i},y_{i})$ gives the position of the beacon nodes. Note that for
the implementation of trilateration algorithm, position of at least three
beacon nodes is required.

###  II-C Kalman Filtering

The estimated position, $\hat{P}$, is then filtered through a Kalman filter to
reduce the effects of the noise. The Kalman filter implementation has two
phases. The first phase is the prediction phase where the initial current
state estimate and the error covariance are computed. The initial current
state can be calculated by using the estimated location by the following
equation:

$\hat{\hat{P}}=S_{T}\hat{P}+\Pi$ (5)

where $\hat{\hat{P}}=(\hat{\hat{x}},\hat{\hat{y}})^{T}$ is the initial current
state estimate computed from the previous estimate $\hat{P}$, $S_{T}$, $S_{T}$
is state transition matrix and $\Pi$ is the control matrix initialized to
zero. The error covariance matrix can then be computed as

$\hat{E}=S_{T}E_{int}S_{T}^{T}+Q$ (6)

where $E_{int}$ is the initial error covariance (supposed to be zero in our
case), and $Q$ is process noise covariance matrix.

The second phase of the Kalman filter implementation is the corrector phase
and is used to estimate actual position ($P$). Kalman corrector phase is
mathematically given by the following equation:

$P=\hat{\hat{P}}+K_{k}(z_{k}-H\hat{\hat{P}})\\\ $ (7)

where $K_{k}$ is Kalman gain expressed in eq. (9), $H$ is the observation
matrix and $z_{k}$ is the measurement vector given by following equation

$z_{k}=\left(\\!\begin{array}[]{c}\sqrt{(\hat{x}-x_{1})^{2}+(\hat{y}-y_{1})^{2}}\\\
\sqrt{(\hat{x}-x_{2})^{2}+(\hat{y}-y_{2})^{2}}\\\
\sqrt{(\hat{x}-x_{3})^{2}+(\hat{y}-y_{3})^{2}}\end{array}\\!\right)$ (8)

$K_{k}=\frac{\hat{E}H^{T}}{H\hat{E}H^{T}+R}\\\ $ (9)

In equation 9, $R$ is the estimated measurement error covariance
(environmental noise) and $\hat{E}$ is the predicted error covariance. The
environmental noise matrix describes the noise inferred on data from the
sources that lie within the path from the sensed object to the filter. Error
covariance is iteratively updated using the equation 10.

$\hat{E}=(1-K_{k}H)\hat{E}$ (10)

TABLE II: Classifications of Proposals for Localization in WSNs [32] PROPOSALS |  RangeBased$/$RangeFree |  AnchorBased$/$AnchorFree |  Distributed$/$Centralized
---|---|---|---
Ren C. Luo Fellow, et al.[1] |  RangeBased |  AnchorBased |  Both
D. Niculesu and B. Nath[7] |  RangeBased |  AnchorBased |  Distributed
Miao Jin, et al.[8] |  RangeFree |  AnchorFree |  Distributed
Koen Langendoen, et al.[9] |  Both |  AnchorBased |  Distributed
E. S. Navarro, et al. [10] |  RangeFree |  AnchorBased |  Distributed
Yi Shang, et al.[2] |  RangeFree |  AnchorBased |  Centralized
Yi Shang, et al.[3] |  RangeFree |  AnchorFree |  Centralized
Anushiya A Kannan, et al.[4] |  RangeFree |  AnchorBased |  Centralized
C. Alippi, et al.,[5] |  RangeBased |  AnchorBased |  Centralized
T. He, et al.,[11] |  RangeFree |  AnchorBased |  Distributed
A. Savvides, et al.[12] |  RangeBased |  AnchorBased |  Distributed
S. Simic, et al.[13] |  RangeFree |  AnchorBased |  Distributed
J. Bachrach, et al.[14] |  RangeFree |  AnchorFree |  Distributed
Nissanka B. Priyantha, et al.[15] |  RangeFree |  AnchorFree |  Distributed
D. Moore, et al.,[16] |  RangeFree |  AnchorFree |  Distributed
L. Meertens, et al.,[17] |  RangeFree |  AnchorFree |  Distributed
King-Yip Cheng, et al.,[18] |  RangeFree |  AnchorBased |  Distributed
A. A. Ahmed, et al.,[19], |  RangeBased |  Both |  Distributed
M. Maroti, et al.,[20], |  RangeBased |  AnchorBased |  Distributed
Neal Patwari, et al.[21], |  RangeBased |  AnchorFree |  Distributed
R. Huang, et al.,[22], |  RangeBased |  AnchorBased |  Distributed
N. A. Alsindi, et al.,[23] |  RangeBased |  AnchorBased |  Distributed
J. Lloret, et al.,[24] |  RangeBased |  AnchorBased |  Distributed
Ren C. Luo Fellow, et al.[6] |  RangeBased |  AnchorBased |  Both

##  III Hardware Implementation of the Proposed Algorithm

In this section, we describe the complete software and hardware implementation
of localization algorithm. We make use of the wireless programming feature of
the off the shelf SYNAPE sensor mote to program them Over-the-Air. The
software used for programming is named as ‘portal’ and is a the SYNAPSE
designated software. All the nodes can be programmed simultaneously via
portal. Each node is capable of receiving RSSI values from its neighboring
nodes, distributed in the region of interest (ROI).

Remote Procedure Calls (RPCs) are transmitted by mobile (target) node on all
of ZigBee channels. The mobile node then broadcasts a request to all reference
nodes which are in range of the target node to receive their RSSI values.
Thereafter, the target node tries to find out the channel with minimum RF
interference from Wifi radio transmitters co-located in the environment. The
built in functions of SYNAPSE motes can be used to find out the channel from
which the target is receiving minimum mean energy. The RSSI value for each
anchor or beacon node is measured at $100ms$ intervals and then averaged out
over a delay of $1sec$. The aggregated RSSI value is then fed into the
localization algorithm.

###  III-A Channel Selection

In order to minimize CTI, channels receiving minimum RF energy gets selected.
The procedure for channel selection has been shown in Fig. 3. First of all,
the target node scans energy on all the ZigBee channels and acquires RSSI with
some sampling rate. The acquired values are then averaged to minimize the
effect of random fluctuations. Thereafter, the target node selects the channel
with minimum interference and initializes this channel in active mode to
establish communication with anchor nodes. Target node monitors this active
channel continuously for any possible interference. As soon as the
interference is detected on this active channel, i.e. the packet failure ratio
crosses a certain set threshold, the process of channel selection gets
repeated (see Fig. 3).

Figure 3: Procedure of Channel Selection

###  III-B Implementation of Localization Algorithm

As mentioned previously, the localization algorithm has been implemented using
off the shelf SYNAPSE sensor motes [26]. Experimental setup has been presented
in the Fig. 4 where the target node is attached to a Laptop where SYNAPSE
Portal software is running. Target node scans all ZigBee channels using built
in functions and selects the channel with minimum interference, as described
previously. After selection of channel with minimum RF interference, target
nodes communicates to its neighbors and acquires the RSSI values of at least
three neighbors (beacon) nodes. Thereafter, trilateration localization
technique is used to calculate the position of target node.
The mobile node can also be programmed without connecting it to the laptop
using SNAPpy language through the Portal’s Over-the-Air programming feature.
The localization algorithm however, remains the same. The target first
automatically scans the ZigBee channels and selects one channel for
communication with beacon nodes. After getting average RSSI values from at
least three beacons it implements trilateration algorithm to calculate its
position and uses Kalman Filter for improved position accuracy.

Figure 4: Experimental Setup

##  IV Experimental Results and Discussions

A snapshot of trilateration localization algorithm, implemented in the absence
of Wifi interference with the SYNAPSE sensor motes, has been shown in Fig. 5,
where green is the target node and red nodes are anchor nodes. If the target
node receives RSSI from more than three neighbor nodes, target node selects
three neighbors with maximum RSSI. Log Distance Path Loss model (eq. 1) is
then used to find out its distances to anchor nodes and its location using
trilateration algorithm. Thereafter, Kalman filter is implemented using
equations 5 and 6 to minimize the mean squared error of the estimated position
and improve the localization accuracy. As shown in Fig. 5, anchor nodes have
positions (0,0), (30,0) and (15, 30) in cartesian coordinates respectively.
Target node receives RSSI of $-60$ dBm from all anchor nodes where as the
reference RSSI is measured to be $-45$ dBm at $1$m distance.

Figure 5: Localization using Trilateration Approach

The experiments are then conducted in the presence of RF interference from
Wifi transceivers. Using the built in channel analyzer tool for ZigBee motes,
RSSI values, prior to any transmission, detected on all channels have been
shown in Fig. 6. RSSI values for channels 11-26 have been shown in the figure
but channel 20 has lowest variations in RSSI values w.r.t. time. Therefore,
channel 20 has been selected for Zigbee transmission by the target node to
communicate with the anchor nodes. Once the channel gets selected,
trilateration localization algorithm is invoked in a similar manner as in the
case of no interference.

Figure 6: RSSI Variations on ZigBee Channels

Fig. 7 presents the results of the trilateration algorithm with and without
applying the averaging function. The curve also presents the result of
localization algorithm after employing both averaging as well as Kalman
filter. The deviation of the estimated position from the original position can
be compared for different schemes. If we simply use Trilateration technique to
estimate target position, accurate estimation of the target position is not
possible. If we find estimated position of target node using Trilateration
technique with the averaging function, we get a better estimate of the
original position but still the deviation cannot be ignored (see Fig. 7).
Finally, if we apply Kalman filter along with the averaging function, the
estimated and the original position are in good agreement with each other.
Thus, with Kalman filtering, we get minimal deviation between estimated
position and original positions. The result show that we achieve a
localization accuracy of less than 0.5m with proposed algorithm.

Figure 7: Original Position and Estimated Position of Mobile Node

##  V Node Deployment Strategy

Based on the experimental results, we proposed a nodes deployment strategy for
indoor environment. With this deployment strategy, mobile node will always
have connectivity with at least three beacon nodes to fulfill the requirement
of trilateration based localization technique. As shown in Fig. 8, where green
is the target node and red nodes are beacon nodes. If the target node receives
RSSI from more than three neighbor nodes, target node selects three neighbors
with maximum RSSI. Log Distance Path Loss model (eq. 1) is then used to find
out its distances to anchor nodes and its location using trilateration
algorithm. Using this deployment strategy in the region of interest, mobile
node will always be in the range of at least three beacon nodes.

Figure 8: Node Deployment Strategy

##  VI Conclusion and Future Work

In this paper, a novel RSSI based localization technique has been introduced
and implemented. The proposed scheme minimizes cross technology interference
(CTI)and apply noise reduction filters to achieve very high localization
accuracy. Hardware implementation of the proposed scheme has been carried out
and the result suggest that scheme can easily be implemented on Zigbee based
sensor motes. The combined CTI minimization and noise reduction technique
achieves a localization accuracy of less than 0.5m on commercial off the shelf
sensor motes. Future work includes addressing CTI in networks using ISM band
with the help of Machine Learning algorithms and Kalman Filtering. Accurate
localization implementation over DASH7 sensor motes is also a work in
progress.

## References

  * [1] R. C. Luo, O. Chen, and S. H. Pan, “Mobile user localization in wireless sensor network using grey prediction method,” in _Industrial Electronics Society, 2005. IECON 2005. 31st Annual Conference of IEEE_. IEEE, 2005, pp. 6–pp.
  * [2] Y. Shang and W. Ruml, “Improved mds-based localization,” in _INFOCOM 2004\. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies_ , vol. 4. IEEE, 2004, pp. 2640–2651.
  * [3] Y. Shang, W. Ruml, Y. Zhang, and M. P. Fromherz, “Localization from mere connectivity,” in _Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing_. ACM, 2003, pp. 201–212.
  * [4] A. A. Kannan, G. Mao, and B. Vucetic, “Simulated annealing based wireless sensor network localization,” _Journal of Computers_ , vol. 1, no. 2, pp. 15–22, 2006.
  * [5] C. Alippi and G. Vanini, “A rssi-based and calibrated centralized localization technique for wireless sensor networks,” in _Pervasive Computing and Communications Workshops, 2006. PerCom Workshops 2006. Fourth Annual IEEE International Conference on_. IEEE, 2006, pp. 5–pp.
  * [6] R. C. Luo, O. Chen, and S. H. Pan, “Mobile user localization in wireless sensor network using grey prediction method,” in _Industrial Electronics Society, 2005. IECON 2005. 31st Annual Conference of IEEE_. IEEE, 2005, pp. 6–pp.
  * [7] D. Niculescu and B. Nath, “Dv based positioning in ad hoc networks,” _Telecommunication Systems_ , vol. 22, no. 1-4, pp. 267–280, 2003.
  * [8] M. Jin, S. Xia, H. Wu, and X. Gu, “Scalable and fully distributed localization with mere connectivity,” in _INFOCOM, 2011 Proceedings IEEE_. IEEE, 2011, pp. 3164–3172.
  * [9] K. Langendoen and N. Reijers, “Distributed localization in wireless sensor networks: a quantitative comparison,” _Computer Networks_ , vol. 43, no. 4, pp. 499–518, 2003.
  * [10] E. Stevens-Navarro, V. Vivekanandan, and V. W. Wong, “Dual and mixture monte carlo localization algorithms for mobile wireless sensor networks,” in _Wireless Communications and Networking Conference, 2007. WCNC 2007. IEEE_. IEEE, 2007, pp. 4024–4028.
  * [11] T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher, “Range-free localization schemes for large scale sensor networks,” in _Proceedings of the 9th annual international conference on Mobile computing and networking_. ACM, 2003, pp. 81–95.
  * [12] A. Savvides, H. Park, and M. B. Srivastava, “The bits and flops of the n-hop multilateration primitive for node localization problems,” in _Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications_. ACM, 2002, pp. 112–121.
  * [13] S. N. Simic and S. Sastry, “Distributed localization in wireless ad hoc networks,” _University of California Technical Report_ , 2002.
  * [14] J. Bachrach, R. Nagpal, M. Salib, and H. Shrobe, “Experimental results for and theoretical analysis of a self-organizing global coordinate system for ad hoc sensor networks,” _Telecommunication Systems_ , vol. 26, no. 2-4, pp. 213–233, 2004.
  * [15] N. B. Priyantha, H. Balakrishnan, E. Demaine, and S. Teller, “Anchor-free distributed localization in sensor networks,” in _Proceedings of the 1st international conference on Embedded networked sensor systems_. ACM, 2003, pp. 340–341.
  * [16] D. Moore, J. Leonard, D. Rus, and S. Teller, “Robust distributed network localization with noisy range measurements,” in _Proceedings of the 2nd international conference on Embedded networked sensor systems_. ACM, 2004, pp. 50–61.
  * [17] L. Meertens and S. Fitzpatrick, “The distributed construction of a global coordinate system in a network of static computational nodes from inter-node distances,” _Kestrel Institute TR KES. U_ , vol. 4, 2004.
  * [18] K.-Y. Cheng, K.-S. Lui, and V. Tam, “Localization in sensor networks with limited number of anchors and clustered placement,” in _Wireless Communications and Networking Conference, 2007. WCNC 2007. IEEE_. IEEE, 2007, pp. 4425–4429.
  * [19] A. A. Ahmed, H. Shi, and Y. Shang, “Sharp: A new approach to relative localization in wireless sensor networks,” in _Distributed Computing Systems Workshops, 2005. 25th IEEE International Conference on_. IEEE, 2005, pp. 892–898.
  * [20] M. Maróti, P. Völgyesi, S. Dóra, B. Kusỳ, A. Nádas, Á. Lédeczi, G. Balogh, and K. Molnár, “Radio interferometric geolocation,” in _Proceedings of the 3rd international conference on Embedded networked sensor systems_. ACM, 2005, pp. 1–12.
  * [21] N. Patwari and A. Hero, “Indirect radio interferometric localization via pairwise distances,” in _Proceedings of 3rd IEEE Workshop on Embedded Networked Sensors_. Citeseer, 2006, pp. 26–30.
  * [22] R. Huang, G. V. Záruba, and M. Huber, “Complexity and error propagation of localization using interferometric ranging,” in _Communications, 2007. ICC’07. IEEE International Conference on_. IEEE, 2007, pp. 3063–3069.
  * [23] N. A. Alsindi, K. Pahlavan, and B. Alavi, “An error propagation aware algorithm for precise cooperative indoor localization,” in _Military Communications Conference, 2006. MILCOM 2006. IEEE_. IEEE, 2006, pp. 1–7.
  * [24] J. Lloret, J. Tomas, M. Garcia, and A. Canovas, “A hybrid stochastic approach for self-location of wireless sensors in indoor environments,” _Sensors_ , vol. 9, no. 5, pp. 3695–3712, 2009.
  * [25] C. Noda, S. Prabh, M. Alves, C. A. Boano, and T. Voigt, “Quantifying the channel quality for interference-aware wireless sensor networks.” _SIGBED Review_ , vol. 8, no. 4, pp. 43–48, 2011.
  * [26] “http://www.synapse-wireless.com.”
  * [27] N. C. Tas, C. R. Sastry, and Z. Song, “Ieee 802.15. 4 throughput analysis under ieee 802.11 interference,” in _International Symposium on Innovations and Real Time Applications of Distributed Sensor Networks_ , 2007.
  * [28] G. Yang and Y. Yu, “Zigbee networks performance under wlan 802.11 b/g interference,” in _Wireless Pervasive Computing, 2009. ISWPC 2009. 4th International Symposium on_. IEEE, 2009, pp. 1–4.
  * [29] R. Musaloiu-E and A. Terzis, “Minimising the effect of wifi interference in 802.15. 4 wireless sensor networks,” _International Journal of Sensor Networks_ , vol. 3, no. 1, pp. 43–54, 2008.
  * [30] Y.-T. Chen, C.-L. Yang, Y.-K. Chang, and C.-P. Chu, “A rssi-based algorithm for indoor localization using zigbee in wireless sensor network,” in _Proc. of the 15th International Conference on Distributed Multimedia Systems (DMS 2009)_ , 2009, pp. 70–75.
  * [31] X. Li, Y. Zhang, K. Xu, G. Fan, and H. Wu, “Research of localization and tracking algorithms based on wireless sensor network?” _Journal of Information and Computational Science_ , vol. 8, no. 4, pp. 708–715, 2011.
  * [32] U. Nazir, N. Shahid, M. Arshad, and S. Raza, “Classification of localization algorithms for wireless sensor network: A survey,” in _Open Source Systems and Technologies (ICOSST), 2012 International Conference on_. IEEE, 2012, pp. 1–5.


# Mobile Network Configuration Recommendation using Deep Generative Graph
Neural Network

Shirwan Piroti  , Ashima Chawla  , Tahar Zanouda  Ericsson.
{shirwan.piroti, ashima.chawla<EMAIL_ADDRESS>
###### Abstract

There are vast number of configurable parameters in a Radio Access Telecom
Network. A significant amount of these parameters is configured by Radio Node
or cell based on their deployment setting. Traditional methods rely on domain
knowledge for individual parameter configuration, often leading to sub-optimal
results. To improve this, a framework using a Deep Generative Graph Neural
Network (GNN) is proposed. It encodes the network into a graph, extracts
subgraphs for each RAN node, and employs a Siamese GNN (S-GNN) to learn
embeddings. The framework recommends configuration parameters for a multitude
of parameters and detects misconfigurations, handling both network expansion
and existing cell reconfiguration. Tested on real-world data, the model
surpasses baselines, demonstrating accuracy, generalizability, and robustness
against concept drift.

###### Index Terms:

Telecom Network Configuration Management, AI, Siamese Neural Network, Graph
Neural Network.

##  I  Introduction

Accurate configuration in a Radio Access Network (RAN) is crucial for stable
and reliable connectivity, ensuring Key Performance Indicators (KPIs) are
within acceptable ranges. RAN consists of interconnected Radio Nodes, each
with unique parameters for specific area coverage. Hardware and software
selection depends on the mobile operator and service area requirements, and
are set up with Configuration Management (CM) parameters [1]. RAN Performance
is monitored via Performance Management (PM) counters.

The configuration process in RAN is complex, often involving vendor default
settings and additional adjustments based on deployment scenarios. Deployment
typically includes two stages: Node Provisioning and Post-integration, with
the latter requiring reconfigurations to achieve KPI acceptance. To address
these challenges, this paper introduces a Deep Generative GNN, which aims to
learn optimal parameters from stable networks and recommend configurations for
other network areas. The approach involves three stages:

  * •

Stage I: Graph-based representation of multi-dimensional RAN data.

  * •

Stage II: Creation of subgraphs using a graph-sampling method and training a
Siamese Graph Neural Network (S-GNN) with data from stable networks.

  * •

Stage III: Recommendation of Configuration Values tailored for different
scenarios:

    * –

Expansion: Installing new cells on existing Radio Nodes.

    * –

Greenfield Deployment: Setting up new Radio Nodes in regions without existing
infrastructure.

    * –

Modification: Adjusting existing cells and Radio Nodes to correct
misconfigurations.

The method aims to develop a machine-assisted method for recommending network
configuration parameters, transferring knowledge from stable operational
networks, and identifying telecom system misconfigurations.

The key contributions of this work include:

  1. 1.

Developing an efficient configuration system with minimal manual intervention.

  2. 2.

Representing multidimensional RAN data as vectors in an embedding space.

  3. 3.

Introducing a robust, generalizable one-shot learning solution [2] that
automatically updates with new data.

The paper’s structure is as follows: Section II introduces the methodology,
and Section III details the evaluation metrics. Section IV details the
results. Finally, section V concludes the paper with future research
directions.

##  II Methodology

This section details the model architectures and the method for generating
configuration values. The approach involves three stages, as shown in Figure
1.

###  II-A Data Description

The data for this study is collected from multiple eNBs and gNBs. This section
details how data was collected and processed.

####  II-A1 Feature Values and Pre-processing

For this end, each cell in the telecom network is represented by two feature
vectors in the dataset:

  * •

$x$ \- Predictor values defined during cell planning, including LTE attributes
[1] like Channelbandwidth (data transmission capacity) and Earfcndl (central
downlink frequency channel number), and NR attributes such as bSChannelBwDL
and arfcnDL [1].

  * •

$y$ \- Configuration values displaying network variation, encompassing LTE
attributes [1] like pZeroNominalPusch (target power level received by the eNB
per resource block) and preambleInitialReceivedTargetPower (initial preamble
power value), and NR attributes such as endcUlNrLowQualThresh and
rachPreambleRecTargetPower [1].

Figure 1: Overview of model training and configuration generation for diverse
use cases.

These vectors combine LTE and NR attributes, facilitating model generalization
across different technology deployments (4G, 5G, mixed mode), where N and M
denote the number of LTE and NR cells in the network, respectively, is
defined:

$\displaystyle(X_{LTE},Y_{LTE})=\\{x_{LTE,i},y_{LTE,i}\\}_{i=1}^{N},$
$\displaystyle(X_{NR},Y_{NR})=\\{x_{NR,i},y_{NR,i}\\}_{i=1}^{M},$

The datasets are then preprocessed as described in the following steps:

  * •

normalize values in each set to the range [0,1]

  * •

Concatenate sets:

$\displaystyle(X,Y)=(X_{LTE}||X_{NR},Y_{LTE}||Y_{NR})$

  * •

Impute missing values by concatenating with 0.

###  II-B RAN Graph

The RAN is modeled as an undirected graph $G=(V,E)$ with vertices
$V=\\{V_{i}\\}_{i=1}^{N+M}$, each representing a RAN cell, and edges $E$
defining cell and inter-Radio Node relations, where

$E\subseteq\big{\\{}V_{i},V_{j}:(V_{i},V_{j})\in V^{2},i\not=j\forall 0\leq
i,j\leq N+M\big{\\}}.$

Subgraphs are $G_{i}=(V_{i}\cup\tilde{V}_{i},E_{i})$, with $\tilde{V}_{i}$
being a random uniform sample of neighbors from $N(V_{i})$, the vertices
connected to $V_{i}$. This approach focuses on local neighborhoods for
configuring Radio Nodes or cells.

###  II-C Datasets for inductive Graph Neural Networks

GNNs are a class of machine learning models designed for learning and
reasoning over graph-structured data. Unlike transductive GNNs, inductive GNNs
[3] can generalize to unseen nodes and graphs. They achieve this by leveraging
shared weights and aggregating information from neighboring nodes to learn
node representations. Each subgraph $G_{i}$ has an associated feature set
which is defined as:

$\tilde{X}_{i}=\\{x_{j}\\}_{V_{j}\in V_{i}\bigcup\tilde{V}_{i}}.$ (1)

Also, $y_{i}$ is the vector containing configuration values for the center
cell $V_{j}$ for which the subgraph is constructed around. The dataset is then
defined as:

$\mathcal{D}^{(N+M)}=\\{(G_{i},\tilde{X}_{i},y_{i})\\}_{i=1}^{N+M}$ (2)

###  II-D Model Definition & Architecture

The models implemented in this study are one-shot meta-learners. The main
model is an S-GNN-based model [4] that is trained using self-supervision
through minimization of a contrastive loss. Figure 2 depicts the architecture
of the model. The S-GNN is compared to a Graph Auto-Encoder (GAE) model that
is trained through unsupervised learning.

The S-GNN and the GAE are functions represented by GNNs that are parameterized
by $\omega$ and are defined as:

$\displaystyle
f_{S-GNN_{\omega}}:(G_{i},\tilde{X}_{i})\rightarrow(G_{i},Z_{i}),$ (3)
$\displaystyle f_{GAE_{\omega}}=f_{Decoder_{\omega}}\circ
f_{Encoder_{\omega}}$ (4) $\displaystyle
f_{Encoder_{\omega}}:(G_{i},\tilde{X}_{i})\rightarrow(G_{i},Z_{i}),$ (5)
$\displaystyle
f_{Decoder_{\omega}}:(G_{i},Z_{i})\rightarrow(G_{i},\hat{X}_{i}).$ (6)

$f_{Encoder_{\omega}}$ is the encoder part of the GAE and generates the latent
space representation and $f_{Decoder_{\omega}}$ reconstructs the input from
the latent space. $Z_{i}$ is the set of all embeddings of vertices associated
with subgraph $G_{i}$, where d is a hyperparameter that refers to the
dimension of the latent space.

$Z_{i}=\\{z_{j}\\}_{V_{j}\in
V_{i}\cup\tilde{V}_{i}}and\>z_{j}\in\mathbb{R}^{d}$ (7)

Figure 2: End-to-end model architecture for configuration management
framework.

###  II-E Architecture & Training

The neural networks $f_{s-GNN_{\omega}}$ , $f_{Encoder_{\omega}}$,
$f_{Decoder_{\omega}}$, each compose multi-headed Graph Attention (GATv2Conv)
[5] and aggregates the output of each head using a Feed Forward Network (FFN).

The parameters $\omega$ in $f_{S-GNN_{\omega}}$ are trained with the objective
to minimize the loss with $M$ as a hyperparameter:

$\mathcal{L}_{contrastive}(c_{a,b},z_{a},z_{b})=(1+c_{a,b})||z_{a}-z_{b}||_{2}\\\
+(1-c_{a,b})max(0,M)-||z_{a}-z_{b}||_{2}.$ (8)

$c_{a,b}=2\frac{y_{a}\cdot y_{b}}{(||y_{a}||_{2}||y_{b}||_{2})}-1\\\ $ (9)

$c_{a,b}$ are the labels, indicating how similar two arbitrary cells $V_{a}$
and $V_{b}$ are based on their corresponding configuration setups.
Additionally, Subspace Learning is leveraged to limit the number of training
pairs by identifying the most informative samples [6]. Informative pairs are
composed of ambiguous samples, that is, samples that are close in the
embedding space but belong to different classes.

The parameters $\omega$ in $f_{GAE_{\omega}}$ are trained with the objective
to minimize the loss:

$\mathcal{L}_{reconstruction}=\frac{1}{|\tilde{X}_{n|}}\sum^{|\tilde{X}_{n}|}_{j=1}||x_{j}-\tilde{x_{j}}||_{2}$
(10)

However, only $f_{Encoder_{\omega}}$ will be used to infer the configuration
values.

###  II-F Inference

The function that yields the configuration values for the $k:th$ cell that is
introduced to the network after training is defined as:

$y_{N+M+k}=f((G_{N+M+k},\tilde{X_{N+M+k}})|f_{\omega,D^{(N+M+k-1)}})$ (11)

where $f_{\omega}$ is either $f_{S-GNN_{\omega}}$ or $f_{Encoder_{\omega}}$,
$\mathcal{D}^{(N+M+k-1)}$ is the dataset that includes the N+M samples used
for training and the $k-1$ samples that were introduced after the initial
training.

$\mathcal{F}_{N+M+k}^{(0)}=\\{||z_{N+M+k}-z_{i}||_{2}\\}_{i=1}^{N+M+k-1}=\\{l_{i}\\}_{i=1}^{N+M+k-1}$
(12)

Defines the set of all distances in the latent space from the new cell
$V_{N+M+k}$, to all other existing cells. The configuration values are
generated using one of two methods.

####  II-F1 Using closest semantic subgraph neighbor

The configurations are acquired from the closest semantic subgraph in the
embedding space.

$\hat{y}_{N+M+k}^{(0)}=\operatorname*{argmin}_{y_{m}\sim(G_{m},\tilde{X}_{m},y_{m})}\mathcal{F}^{(0)}_{N+M+k}$
(13)

####  II-F2 Using Majority voting

The configurations is acquired from an aggregation of the node’s $K$ closest
neighbors in the latent space, where $K$ is a pre-defined parameter of
neighbors.

$\mathcal{F}^{(n+1)}_{N+M+k}=\mathcal{F}^{(n)}_{N+M+k}\backslash\\{l^{(n)}_{n+M+k}\\}$
(14)

$l^{(n+1)}_{N+M+k}$ is the $n:th$ smallest value in $F^{0}_{N+M+k}$ and
$\mathcal{F}^{n+1}_{N+M+k}$ is the set of loss values, excluding the set of
losses:

$\\{l^{(n)}\\}^{n-1}_{i=1}$

This yields the configurations, as shown in equation (15).

$\hat{y}_{N+M+k}^{(n)}=\operatorname*{argmin}_{y_{m}\sim(G_{m},\tilde{X}_{m},y_{m})}\mathcal{F}_{N+M+k}^{(n)}$
(15)

where $m$ is an index value of the $y_{m}$ that yields $\hat{y}_{N+M+k}^{(n)}$
which is the $n$:th most optimal set of configuration values. Thus,

$\hat{y}_{N+M+k}^{Majority}=aggregate\big{(}\\{\hat{y}_{N+M+k}^{(n)}\\}_{n=0}^{K-1}\big{)}$
(16)

where aggregate is to be specified per attribute included in $y$.

##  III Evaluation Metrics

This section details metrics used to evaluate the performance of the models.

Figure 3: 2-dimensional representation of the embeddings produced by three
distinct models. Dimension of embeddings are redcued using PCA.

###  III-A Configuration Accuracy Score

The accuracy of the generated configurations by the models across the whole
network is then defined as:

$Accuracy=\frac{1}{N+M}\sum^{N+M}_{j=1}\frac{y_{j}\cdot\hat{y}_{j}}{||y_{j}||_{2}||\hat{y}_{j}||_{2}}$
(17)

Given $\hat{y}_{j}=y_{m}$ are the configuration values for the $m:th$ cell
network that yields the smallest $L_{2}-loss$ with the embedding of cell
$(G_{j},\tilde{X_{j}})$.

###  III-B Misconfiguration Detection Score

Anomaly detection is applied to evaluate the novelty of input samples in the
network, providing operators with confidence values for the generated
configurations. These values are anomaly scores, calculated by a model trained
to identify novelties based on the distribution of embeddings in a latent
space. If this score surpasses a predefined threshold, it signals the operator
to reevaluate the specific instance.

$anomalyScore_{i}=f_{anomaly(z_{i}\sim f_{\omega}(G_{i},\tilde{X_{i}})}).$
(18)

Figure 4 presents the embeddings’ distributions with anomaly scores from
iForest [7], indicating variation in network configurations.

##  IV Results

The paper evaluates two architectures, S-GNN and GAE, across four datasets.
Their performance, measured using Average Optimal Cosine Similarity (17), is
detailed in Table I. Higher scores in this measure correlate with better
configuration prediction in telecom networks. Figure 3 illustrates the models’
14-dimensional embeddings reduced to 2 dimensions via Principal Component
Analysis (PCA), comparing an untrained model, GAE, and S-GNN. This visual
representation highlights the distinct learning patterns of each model. GAE,
an unsupervised model, demonstrates high accuracy in discerning different
deployment contexts in the RAN, despite not being trained on configuration
data. This indicates a strong correlation between the contextual information
it processes and the resulting configurations.

In contrast, S-GNN shows higher accuracy in recognizing configuration setups
when trained on both configuration and contextual data. However, this reliance
on configuration data might lead to decreased adaptability over time as
network settings evolve.

Figure 4 presents the embeddings’ distributions with anomaly scores. Notably,
networks with less configuration variation show higher model accuracy,
suggesting the models, especially S-GNN, perform better in more stable
configuration environments. In summary, while GAE excels in unsupervised
learning from non-configuration data, S-GNN is more accurate in supervised
scenarios but may face challenges in adapting network configurations changes.

Figure 4: S-GNN’s 2D embeddings represent novelty, with highlighted circles (embedding) for highest anomaly scores. Model | Dataset | Accuracy
---|---|---
| Type | Network | Date |
S-GNN | Test | 1 | 2021-12-10 | 0.888
S-GNN | Train | 1 | 2023-03-23 | 0.953
S-GNN | Test | 1 | 2023-07-25 | 0.921
S-GNN | Test | 2 | 2023-03-23 | 0.990
GAE | Test | 1 | 2021-12-10 | 0.906
GAE | Train | 1 | 2023-03-23 | 0.916
GAE | Test | 1 | 2023-07-25 | 0.907
GAE | Test | 2 | 2023-03-23 | 0.991
TABLE I: Accuracy for the GAE and the S-GNN, on 4 distinct datasets. The range
is bounded in the range [0, 1].

##  V Conclusion and Future Direction

In this paper, the proposed framework enables mobile operators to generate a
multitude of values for configuration parameters in telecom networks. At the
core of this framework, a Deep Generative Model combines GNN and Siamese
Neural Network. The framework represents RAN as a graph and then leverages
subgraphs to enable inductive inference. The model generates embeddings which
are used to infer configurations and to detect misconfiguration in the
network. The model was evaluated on multiple datasets from operational
networks. The model yields high accuracy on the datasets, indicating that the
framework is generalizable and robust against concept drift.

In future developments, this work will focus on challenges related to
recommending configurations for O-RAN [8] networks. Additionally, future work
will involve eXplainable Artificial Intelligence (XAI) to demystify AI
decisions, enhancing trust and transparency between machines and users.

## References

  * [1] 3GPP, “3gpp ts 32.300: Telecommunication management; configuration management (cm); name convention for managed objects,” 2024.
  * [2] L. Bertinetto, J. F. Henriques, J. Valmadre, P. Torr, and A. Vedaldi, “Learning feed-forward one-shot learners,” Advances in neural information processing systems, vol. 29, 2016.
  * [3] L. Anghinoni, Y.-t. Zhu, D. Ji, and L. Zhao, “Transgnn: A transductive graph neural network with graph dynamic embedding,” in 2023 International Joint Conference on Neural Networks (IJCNN), pp. 1–8, IEEE, 2023.
  * [4] N. Mehrotra, N. Agarwal, P. Gupta, S. Anand, D. Lo, and R. Purandare, “Modeling functional similarity in source code with graph-based siamese networks,” IEEE Transactions on Software Engineering, vol. 48, no. 10, pp. 3771–3789, 2021.
  * [5] S. Brody, U. Alon, and E. Yahav, “How attentive are graph attention networks?,” arXiv preprint arXiv:2105.14491, 2021.
  * [6] E. Krivosheev, M. Atzeni, K. Mirylenka, P. Scotton, and F. Casati, “Siamese graph neural networks for data integration,” arXiv preprint arXiv:2001.06543, 2020.
  * [7] X. Zhao, Y. Wu, D. L. Lee, and W. Cui, “iforest: Interpreting random forests via visual analytics,” IEEE transactions on visualization and computer graphics, 2018.
  * [8] M. Polese, L. Bonati, S. D’oro, S. Basagni, and T. Melodia, “Understanding o-ran: Architecture, interfaces, algorithms, security, and research challenges,” IEEE Communications Surveys & Tutorials, 2023.


# Randers and $(\alpha,\beta)$ equigeodesics for some compact homogeneous
manifolds

Ju Tan  School of Mathematics and Physics, Anhui University of Technology,
Maanshan, 243032, P.R. China<EMAIL_ADDRESS>and  Ming Xu∗ School of
Mathematical Sciences, Capital Normal University, Beijing 100048, P.R. China
<EMAIL_ADDRESS>
###### Abstract.

A smooth curve on $G/H$ is called a Riemannian equigeodesic if it is a
homogeneous geodesic for all $G$-invariant Riemannian metrics on $G/H$. With
the $G$-invariant Riemannian metric replaced by other classes of $G$-invariant
metrics, we can similarly define Finsler equigeodesic, Randers equigeodesic,
$(\alpha,\beta)$ equigeodesic, etc. In this paper, we study Randers and
$(\alpha,\beta)$ equigeodesics. For a compact homogeneous manifold, we prove
Randers and $(\alpha,\beta)$ equigeodesics are equivalent, and find a
criterion for them. Using this criterion we can classify the equigeodesics on
many compact homogeneous manifolds which permit non-Riemannian homogeneous
Randers metrics, including four classes of homogeneous spheres.

Mathematics Subject Classification(2010): 53C22, 53C30, 53C60.

Keywords: equigeodesic, equigeodesic vector, homogeneous $(\alpha,\beta)$
metric, homogeneous gedesics, homogeneous manifold, homogeneous Randers metric

∗Ming Xu is the corresponding author.

##  1\. Introduction

###  1.1. Homogeneous geodesic and equigeodesic in Riemannian and Finsler
geometry

On a Riemannian manifold, a geodesic is called homogeneous if it is the orbit
of a one-parameter subgroup of isometries. This notion reflects a key
philosophy in Erlanger Programme, i.e., applying Lie theory to the study of
geometry. Many important topics in homogeneous Riemannian geometry are closely
related to the study of homogeneous geodesic. For example, O. Kowalski and L.
Vanhecke defined a Riemannian manifold to be geodesic orbit (or g.o. in
short), if each geodesic is homogeneous [16]. Both g.o. spaces and their
subclasses, normal homogeneous [3, 25] and $\delta$-homogeneous spaces [6],
weakly symmetric spaces [32], etc, have been extensively studied in Riemannian
geometry [1, 2, 10, 12, 14, 22, 25]. Recently, they have been generalized and
studied in Finsler geometry [8, 17, 27, 28, 29, 31, 33].

Equigeodesic was introduced by N. Cohen, L. Grama and C.J.C. Negreiros in 2010
[7]. A smooth curve on a homogeneous space $G/H$ is called an equigeodesic if
it is a homogeneous geodesic for any $G$-invariant metric. When the type of
the metric is specified, Riemannian, Finsler, Randers, $(\alpha,\beta)$, etc,
the corresponding equigeodesic is called a Riemannian equigeodesic, Finsler
equigeodesic, Randers equigeodesic, $(\alpha,\beta)$ equigeoesic, etc,
respectively. Until now, only Riemannian equigeodesic has been studied for
some special homogeneous spaces, flag manifolds, spheres, etc [13, 23, 26].
Finsler and other types of equigeodesic are also worthy to be studied because
they represent different algebraic properties.

###  1.2. Reduction to equigeodesic vector

A vector $X\in\mathfrak{g}$ is called a Riemannian equigeodesic vector for
$G/H$ if it generates a Riemannian equigeodesic $c(t)=\exp tX\cdot o$ passing
$o=eH$.

By homogeneity, the study for Riemannian equigeodesic can be reduced to that
for Riemannian equigeodesic vector. Further reduction need more assumptions
for $G/H$.

In this paper, we only consider a homogeneous manifold $G/H$ with a compact
$(G,\langle\cdot,\cdot\rangle_{\mathrm{bi}})$, in which
$\langle,\rangle_{\mathrm{bi}}$ is an $\mathrm{Ad}(G)$-invariant inner product
on $\mathfrak{g}$. We denote $\mathfrak{g}=\mathfrak{h}+\mathfrak{m}$ the
corresponding orthogonal reductive decomposition, and use subscripts
$\mathfrak{h}$ and $\mathfrak{m}$ for projections to each subspace. Then any
$G$-invariant Riemannian on $G/H$ is one-to-one determined by an
$\mathrm{Ad}(H)$-invariant inner product

$\alpha(u,v)=\langle u,\Lambda(v)\rangle_{\mathrm{bi}},\quad\forall
u,v\in\mathfrak{m},$

in which $\Lambda:\mathfrak{m}\rightarrow\mathfrak{m}$ is called the metric
operator.

By the criterion for geodesic vector [16], $X\in\mathfrak{g}$ is a Riemannian
equigeodesic for $G/H$ if and only if $X\notin\mathfrak{h}$ and

$[\Lambda(X_{\mathfrak{m}}),X]_{\mathfrak{m}}=0,\quad\forall\Lambda,$ (1.1)

where the metric operator $\Lambda$ exhausts all $\mathrm{Ad}(H)$-invariant
$\langle\cdot,\cdot\rangle_{\mathrm{bi}}$-positive definite linear
endomorphisms on $\mathfrak{m}$. In particular, we can take
$\Lambda=\mathrm{Id}$, then (1.1) implies, when $X$ is a Riemannian
equigeodesic vector, $X_{\mathfrak{h}}$ and $X_{\mathfrak{m}}$ commute, and
then $X_{\mathfrak{m}}$ is also a Riemannian equigeodesic vector which
generates the same curve $c(t)=\exp tX_{\mathfrak{m}}\cdot o=\exp tX\cdot o$
as $X$.

To summarize, the study of (Riemannian) equigeodesics for $G/H$ can be reduced
to that of (Riemannian) equigeodesic vectors which are contained in
$\mathfrak{m}$. Finsler, Randers, $(\alpha,\beta)$ (and other types of)
equigeodesic vectors can be defined similarly, i.e., $X\in\mathfrak{g}$ which
generates an equigeodesic $c(t)=\exp tX\cdot o$ of the specified type.
Obviously they are also Riemannian equigeodesic vectors. So above reduction is
still valid.

###  1.3. Main results

In this paper, we mainly discuss Randers and $(\alpha,\beta)$ equigeodesics.
Firstly, we prove they are equivalent for a compact homogeneous manifold.

######  Theorem 1.1.

Let $G/H$ be a homogeneous manifold with a compact Lie group
$(G,\langle\cdot,\cdot\rangle_{\mathrm{bi}})$ and the corresponding orthogonal
reductive decomposition $\mathfrak{g}=\mathfrak{h}+\mathfrak{m}$. Suppose that
$\mathfrak{m}$ can be further $\mathrm{Ad}(H)$-invariantly decomposed as
$\mathfrak{m}=\mathfrak{m}_{0}+\mathfrak{m}^{\prime}$, in which
$\mathfrak{m}_{0}\neq 0$ is the fixed point set for the
$\mathrm{Ad}(H)$-action on $\mathfrak{m}$. Then for any
$X\in\mathfrak{m}\backslash\\{0\\}$, the following statements are equivalent:

  1. (1)

$X$ is an $(\alpha,\beta)$ equigeodesic vector;

  2. (2)

$X$ is a Randers equigeodesic vector;

  3. (3)

$X$ is a Riemannian equigeodesic vector and
$[X,\mathfrak{m}_{0}]\subset\mathfrak{h}$.

As applications of Theorem 1.1, we can classify Randers and $(\alpha,\beta)$
equigeodesic vectors on some compact homogeneous manifolds. To avoid
iteration, $(\alpha,\beta)$ equigeodesic or $(\alpha,\beta)$ equigeodesic
vector will not be mentioned later. We only concern those homogeneous
manifolds which admits non-Riemannian homogeneous Randers metrics, otherwise
there is no new story.

######  Theorem 1.2.

Let $H\subsetneqq K\subsetneqq(G,\langle\cdot,\cdot\rangle_{\mathrm{bi}})$ be
a triple of distinct compact connected Lie groups, such that $G/K$ is strongly
isotropy irreducible, and $H$ is normal in $K$. Denote $\mathfrak{m}_{0}$ and
$\mathfrak{m}^{\prime}$ the
$\langle\cdot,\cdot\rangle_{\mathrm{bi}}$-orthogonal complements of
$\mathfrak{h}$ in $\mathfrak{k}$ and $\mathfrak{k}$ in $\mathfrak{g}$
respectively. Suppose that neither $\mathfrak{h}$ nor $\mathfrak{m}_{0}$ is an
ideal of $\mathfrak{g}$. Then the set of all Randers equigeodesic vectors for
$G/H$ which are contained in
$\mathfrak{m}=\mathfrak{m}_{0}+\mathfrak{m}^{\prime}$ is
$\mathfrak{c}(\mathfrak{m}_{0})\backslash\\{0\\}$.

By the classification of compact irreducible symmetric spaces [15] and compact
strongly isotropy irreducible spaces [18, 19, 20, 24], almost all $G/H$’s in
Theorem 1.2 have no Randers equigeodesics or Randers equigeodesic vectors,
except those associated with compact irreducible Hermitian symmetric
$G/K=G/(U(1)H)$, i.e.,

$\displaystyle G/H$ $\displaystyle=$ $\displaystyle
SU(n_{1}+n_{2})/SU(n_{1})SU(n_{2}),\ Sp(n)/SU(n),\ SO(n+2)/SO(n),$ (1.2)
$\displaystyle SO(2n)/SU(n),\ E_{6}/SO(10),\ E_{7}/E_{6},$

have a line $\mathfrak{m}_{0}\backslash\\{0\\}$ of Randers equigeodesic
vectors. As Theorem 1.2 has not assumed any effectiveness for the $G$-action
on $G/K$, it can also tell us that the set of Randers equigeodesic vectors for
$U(1)G/U(1)H$ with $G/H$ in (1.2), which are contained in $\mathfrak{m}$, is
the line $\mathfrak{m}_{0}\backslash\\{0\\}$.

Finally, we give a classification of Randers equigeodesics for homogeneous
spheres which permit non-Riemannian homogeneous Randers metrics.

######  Theorem 1.3.

Let $G/H$ be a homogeneous sphere on which the compact connected Lie group
$(G,\langle,\rangle_{\mathrm{bi}})$ acts effectively. Denote
$\mathfrak{g}=\mathfrak{h}+\mathfrak{m}$ the corresponding orthogonal
reductive decomposition and assume $G/H$ admits non-Riemannian $G$-invariant
Randers metrics, i.e., the fixed point set $\mathfrak{m}_{0}$ for the
$\mathrm{Ad}(H)$-action on $\mathfrak{m}$ is not zero. Then we have the
following:

  1. (1)

the set of Randers equigeodesic vectors for $G/H$ which is contained in
$\mathfrak{m}$ is $\mathfrak{m}_{0}\backslash\\{0\\}$ when
$G/H=SU(n+1)/SU(n)$, $U(n+1)/U(n)$ or $Sp(n+1)U(1)/Sp(n)U(1)$;

  2. (2)

$G/H=Sp(n+1)/Sp(n)$ has no Randers equigeodesics or Randers equigeodesic
vectors.

These results implies that studying equigeodesic in a Finsler context might be
even easier sometimes, where cleaner classification lists would be more
achievable.

This paper is organized as following. In Section 2, we summarize some
necessary knowledge on homogeneous Randers and $(\alpha,\beta)$ spaces and
prove Theorem 1.1. In Section 3, we prove Theorem 1.2 and Theorem 1.3 as
applications of Theorem 1.1.

##  2\. Randers and $(\alpha,\beta)$ equigeodesic

###  2.1. Homogeneous Randers and $(\alpha,\beta)$ spaces

Let $G/H$ be a homogeneous manifold with a reductive decomposition
$\mathfrak{g}=\mathfrak{h}+\mathfrak{m}$. We decompose $\mathfrak{m}$
$\mathrm{Ad}(H)$-equivariantly as
$\mathfrak{m}=\mathfrak{m}_{0}+\mathfrak{m}^{\prime}$, in which
$\mathfrak{m}_{0}$ is the fixed point set for the $\mathrm{Ad}(H)$-action on
$\mathfrak{m}$.

Any $G$-invariant $(\alpha,\beta)$ metric $F$ on $G/H$ is one-to-one
determined by the $\mathrm{Ad}(H)$-invariant Minkowski norm in the tangent
space at $o=eH$, which can be presented as

$F(y)=\alpha(y,y)^{1/2}\varphi(\tfrac{\alpha(y,u)}{\alpha(y,y)^{1/2}}).$ (2.3)

Here $\alpha$ is an $\mathrm{Ad}(H)$-invariant inner product on
$\mathfrak{m}$, $u$ is a nonzero vector in $\mathfrak{m}_{0}$ and
$\varphi=\varphi(s)$ is a positive smooth function for $|s|\leq
b=\alpha(u,u)^{1/2}$ with the inequality

$\varphi(s)-s\varphi^{\prime}(s)+(b^{2}-s^{2})\varphi^{\prime\prime}(s)>0$

satisfied everywhere. In particular, this homogeneous metric $F$ is Randers
when $\varphi(s)=1+s$, which is of the form

$F(y)=\alpha(y,y)^{1/2}+\alpha(y,u).$ (2.4)

A vector $X\in\mathfrak{g}$ is called a geodesic vector for $(G/H,F)$ if
$c(t)=\exp tX\cdot o$ is a homogeneous geodesic. When $F$ is $(\alpha,\beta)$
or Randers, we have the following criterion for geodesic vectors (see
Proposition 3.4 in [30]).

######  Lemma 2.1.

Keep all assumptions and notations in this subsection. Then $X\in\mathfrak{g}$
is a geodesic vector of the homogeneous $(\alpha,\beta)$ metric $F$ in (2.3)
if and only if $X\notin\mathfrak{h}$ and

$\alpha([X,Z]_{\mathfrak{m}},(\varphi(s)-s\varphi^{\prime}(s))X_{\mathfrak{m}}+\varphi^{\prime}(s)\alpha(X_{\mathfrak{m}},X_{\mathfrak{m}})^{1/2}u)=0,\quad\forall
Z\in\mathfrak{m},$ (2.5)

where
$s=\tfrac{\alpha(X_{\mathfrak{m}},u)}{\alpha(X_{\mathfrak{m}},X_{\mathfrak{m}})^{1/2}}$.
In particular, when $\varphi(s)=1+s$, (2.5) can be simplified as

$\alpha([X,Z]_{\mathfrak{m}},X_{\mathfrak{m}}+\sqrt{\alpha(X_{\mathfrak{m}},X_{\mathfrak{m}})}u)=0.$
(2.6)

See [5, 8, 31] for more details on general and homogeneous Finsler geometry,
as well as the related homogeneous geodesic and g.o. property.

###  2.2. Proof of Theorem 1.1

Firstly, the argument from (1) to (2) is obvious because each Randers metric
is an $(\alpha,\beta)$ metric.

Nextly, we prove the statement from (2) to (3). Let
$\alpha(\cdot,\cdot)=\langle\cdot,\Lambda(\cdot)\rangle_{\mathrm{bi}}$ be any
$\mathrm{Ad}(H)$-invariant inner product on $\mathfrak{m}$, and $u$ any vector
in $\mathfrak{m}_{0}$. Then the Rander equigeodesic vector
$X\in\mathfrak{m}\backslash\\{0\\}$ is a geodesic vector for the homogeneous
Randers metric $F(y)=\alpha(y,y)^{1/2}+\alpha(y,u)$. Applying (2.6) in Lemma
2.1, we get

$\alpha([X,Z]_{\mathfrak{m}},X)+\alpha(X,X)^{1/2}\alpha([X,Z]_{\mathfrak{m}},u)=0.$
(2.7)

Obviously the Randers equigeodesic vector $X$ is a Riemannian equigeodesic
vector, i.e., $\alpha([X,\mathfrak{m}]_{\mathfrak{m}},X)=0$. So we have

$\displaystyle
0=\alpha([X,\mathfrak{m}]_{\mathfrak{m}},u)=\langle[X,\mathfrak{m}],\Lambda(u)\rangle_{\mathrm{bi}}=\langle\mathfrak{m},[X,\Lambda(u)]\rangle_{\mathrm{bi}},$

i.e., $[X,\Lambda(u)]\subset\mathfrak{h}$. By Schur lemma, the metric operator
$\Lambda$ for $\alpha$ must be of the form
$\Lambda=\Lambda_{0}\oplus\Lambda^{\prime}$ in which $\Lambda_{0}$ is any
arbitrary $\langle\cdot,\cdot\rangle_{\mathrm{bi}}$-positive definite linear
endomorphism on $\mathfrak{m}_{0}$ and $\Lambda^{\prime}$ is some endomorphism
on $\mathfrak{m}^{\prime}$. As we have assumed $u\neq 0$,
$\Lambda(u)=\Lambda_{0}(u)$ exhausts an open neighborhood of $u$ in
$\mathfrak{m}_{0}$. So we get $[X,\mathfrak{m}_{0}]\subset\mathfrak{h}$.

This ends the proof from (2) to (3).

Finally, we prove the statement from (3) to (1). Let $F$ be any $G$-invariant
$(\alpha,\beta)$ metric on $G/H$, determined by the Minkowski norm
$F(y)=\alpha(y,y)^{1/2}\varphi(\tfrac{\alpha(y,u)}{\alpha(y,y)^{1/2}})$ on
$\mathfrak{m}$. Since the Riemannian equigeodesic vector $X$ is a geodesic
vector for the $G$-invariant Riemannian metric $\alpha$, we have

$\alpha([X,Z]_{\mathfrak{m}},X)=0,\quad\forall Z\in\mathfrak{m}.$ (2.8)

As we have observed, the metric operator $\Lambda$ of $\alpha$ preserves
$\mathfrak{m}_{0}$. So we have

$\displaystyle\alpha([X,\mathfrak{m}]_{\mathfrak{m}},u)=\langle[X,\mathfrak{m}],\Lambda(u)\rangle_{\mathrm{bi}}=\langle\mathfrak{m},[X,\Lambda(u)]\rangle_{\mathrm{bi}}\subset\langle\mathfrak{m},[X,\mathfrak{m}_{0}]\rangle_{\mathrm{bi}}\subset\langle\mathfrak{m},\mathfrak{h}\rangle_{\mathrm{bi}}=0.$
(2.9)

Summarizing (2.8) and (2.9), we get (2.5) in Lemma 2.1, i.e., $X$ is a
geodesic vector for $F$. Since the $G$-invariant $(\alpha,\beta)$-metric $F$
is arbitrarily chosen, $X$ is an $(\alpha,\beta)$ equigeodesic vector.

This ends the proof from (3) to (1).

##  3\. Applications of Theorem 1.1

###  3.1. Proof of Theorem 1.2

We keep all relevant assumptions and notations for Theorem 1.2. Then
$\mathfrak{g}=\mathfrak{k}+\mathfrak{m}^{\prime}$ and
$\mathfrak{g}=\mathfrak{h}+\mathfrak{m}=\mathfrak{h}+(\mathfrak{m}_{0}+\mathfrak{m}^{\prime})$
are $\langle\cdot,\cdot\rangle_{\mathrm{bi}}$-orthogonal reductive
decompositions for $G/K$ and $G/H$ respectively. Together with the ideal
decomposition $\mathfrak{k}=\mathfrak{h}\oplus\mathfrak{m}_{0}$, they provide
the following bracket relations:

$[\mathfrak{h},\mathfrak{m}^{\prime}]\subset\mathfrak{m}^{\prime},\quad[\mathfrak{m}_{0},\mathfrak{m}^{\prime}]\subset\mathfrak{m}^{\prime},\quad[\mathfrak{h},\mathfrak{m}_{0}]=0,\quad[\mathfrak{h},\mathfrak{h}]\subset\mathfrak{h},\quad[\mathfrak{m}_{0},\mathfrak{m}_{0}]\subset\mathfrak{m}_{0}.$
(3.10)

It implies that the decomposition
$\mathfrak{m}=\mathfrak{m}_{0}+\mathfrak{m}^{\prime}$ is
$\mathrm{Ad}(H)$-invariant. Because $\mathfrak{m}_{0}$ is not an ideal of
$\mathfrak{g}$, $\mathfrak{m}_{0}\neq 0$, i.e., $G/H$ admits $G$-invariant
non-Riemannian Randers metrics. The next lemma implies that $\mathfrak{m}_{0}$
is the fixed point set for the $\mathrm{Ad}(H)$-action on $\mathfrak{m}$.

######  Lemma 3.1.

Any vector $v\in\mathfrak{m}^{\prime}$ satisfying $[v,\mathfrak{h}]=0$ or
$[v,\mathfrak{m}_{0}]=0$ must be 0.

Proof. Firstly, we prove $v\in\mathfrak{m}^{\prime}$ satisfying
$[v,\mathfrak{m}_{0}]=0$ must vanish. Assume conversely $v\neq 0$, then (3.10)
implies that the nonzero subspace
$\mathfrak{c}_{\mathfrak{m}^{\prime}}(\mathfrak{m}_{0})\subset\mathfrak{m}^{\prime}$
is $\mathrm{ad}(\mathfrak{k})$-invariant. By the strongly isotropy
irreducibility of $G/K$, we must have
$\mathfrak{c}_{\mathfrak{m}^{\prime}}(\mathfrak{m}_{0})=\mathfrak{m}^{\prime}$,
i.e., $[\mathfrak{m}^{\prime},\mathfrak{m}_{0}]=0$. Together with
$[\mathfrak{k},\mathfrak{m}_{0}]\subset\mathfrak{m}_{0}$, it implies that
$\mathfrak{m}_{0}$ is an ideal of $\mathfrak{g}$. This contradicts the
assumption in Theorem 1.2.

Nextly, we prove $v\in\mathfrak{m}^{\prime}$ satisfying $[v,\mathfrak{h}]=0$
must vanish. Assume conversely that it does not, then similar argument shows
that
$\mathfrak{c}_{\mathfrak{m}^{\prime}}(\mathfrak{h})=\mathfrak{m}^{\prime}$.
Then $\mathfrak{h}$ is an ideal of $\mathfrak{g}$, but this contradicts the
assumption in Theorem 1.2.

Proof of Theorem 1.2. Firstly, we prove that any
$X\in\mathfrak{c}(\mathfrak{m}_{0})\backslash\\{0\\}$ is a Randers
equigeodesic vector. Lemma 3.1 indicates that $\mathfrak{m}^{\prime}$ does not
contain any trivial sub-representation for the $\mathrm{Ad}(H)$-action. By
Schur Lemma, the metric operator $\Lambda$ for a $G$-invariant Riemannian
metric on $G/H$ must be of the form
$\Lambda=\Lambda_{0}\oplus\Lambda^{\prime}$, in which each $\Lambda_{0}$ and
$\Lambda^{\prime}$ are linear endomorphisms on $\mathfrak{m}_{0}$ and
$\mathfrak{m}^{\prime}$ respectively. So for every metric operator $\Lambda$,
we have

$[\Lambda(X),X]_{\mathfrak{m}}\subset[\mathfrak{m}_{0},\mathfrak{c}(\mathfrak{m}_{0})]_{\mathfrak{m}}=0,$

which proves $X$ is a Riemannian equigeodesic vector. Meanwhile, it is obvious
that $[X,\mathfrak{m}_{0}]=0\subset\mathfrak{h}$. By Theorem 1.1,
$X\in\mathfrak{c}(\mathfrak{m}_{0})\backslash\\{0\\}$ is a Randers
equigeodesic vector.

Nextly, we prove there are no other Randers equigeodesic vectors. Suppose
$X=X_{0}+X^{\prime}\in\mathfrak{m}\backslash\\{0\\}$ with
$X_{0}\in\mathfrak{m}_{0}$ and $X^{\prime}\in\mathfrak{m}^{\prime}$ is a
Randers equigeodesic vector. By Theorem 1.1,

$[X,v]=[X_{0},v]+[X^{\prime},v]\in\mathfrak{h},\quad\forall
v\in\mathfrak{m}_{0}.$ (3.11)

However, (3.10) indicates that
$[X_{0},v]+[X^{\prime},v]\in\mathfrak{m}_{0}+\mathfrak{m}^{\prime}$ for
$v\in\mathfrak{m}_{0}$. So we must have
$[X_{0},\mathfrak{m}_{0}]=[X^{\prime},\mathfrak{m}_{0}]=0$, i.e.,
$X_{0}\in\mathfrak{c}(\mathfrak{m}_{0})$, and by Lemma 3.1, $X^{\prime}=0$.

This ends the proof of Theorem 1.2.

###  3.2. Proof of Theorem 1.3

The classification for homogeneous spheres [4, 21] can be summarized as Table
1, where we list the decomposition of each $\mathfrak{m}$, where
$\mathfrak{m}_{0}\neq 0$ is a trivial $H$-representation, and
$\mathfrak{m}_{i}$’s with $i>0$ are distinct nontrivial irreducible
$H$-representations.

No. | Spheres | $G$ | $H$ | Isotropy rep.
---|---|---|---|---
1 | $\mathrm{S}^{n}$ | ${SO}(n+1)$ | ${SO}(n)$ | irred
2 | $\mathrm{S}^{2n+1}$ | ${SU}(n+1)$ | ${SU}(n)$ | $\mathfrak{m}=\mathfrak{m}_{0}\oplus\mathfrak{m}_{1}$
3 | $\mathrm{S}^{2n+1}$ | $U(n+1)$ | $U(n)$ | $\mathfrak{m}=\mathfrak{m}_{0}\oplus\mathfrak{m}_{1}$
4 | $\mathrm{S}^{4n+3}$ | ${Sp}(n+1)$ | ${Sp}(n)$ | $\mathfrak{m}=\mathfrak{m}_{0}\oplus\mathfrak{m}_{1}$
5 | $\mathrm{S}^{4n+3}$ | ${Sp}(n+1){Sp}(1)$ | ${Sp}(n){Sp}(1)$ | $\mathfrak{m}=\mathfrak{m}_{1}\oplus\mathfrak{m}_{2}$
6 | $\mathrm{S}^{4n+3}$ | ${Sp}(n+1)U(1)$ | ${Sp}(n)U(1)$ | $\mathfrak{m}=\mathfrak{m}_{0}\oplus\mathfrak{m}_{1}\oplus\mathfrak{m}_{2}$
7 | $\mathrm{S}^{15}$ | $\mathrm{Spin}(9)$ | $\mathrm{Spin}(7)$ | $\mathfrak{m}=\mathfrak{m}_{1}\oplus\mathfrak{m}_{2}$
8 | $\mathrm{S}^{7}$ | $\mathrm{Spin}(7)$ | $G_{2}$ | irred
9 | $\mathrm{S}^{7}$ | $G_{2}$ | ${SU}(3)$ | irred
Table 1. Classification for homogeneous spheres

We only concern those with $\mathfrak{m}_{0}$, which admits non-Riemannian
$G$-invariant Randers metrics. So $G/H$ is one of the following:

$\displaystyle S^{2n+1}=U(n+1)/U(n),\ S^{2n+1}=SU(n+1)/SU(n),$ $\displaystyle
S^{4n+3}=Sp(n+1)/Sp(n),\ S^{4n+3}=Sp(n+1)U(1)/Sp(n)U(1).$

Case 1: $G/H=SU(n+1)/SU(n)$ or $U(n+1)/U(n)$.

In this case, $\dim\mathfrak{m}_{0}=1$ and $G/H$ is associated with the
Hermitian symmetric space $G/K=SU(n+1)/S(U(n)U(1))$ or $U(n+1)/(U(n)U(1))$,
Theorem 1.2 tells us that the set of Randers equigeodesic vectors which are
contained in $\mathfrak{m}$ is the line $\mathfrak{m}_{0}\backslash\\{0\\}$.

Case 2: $G/H=Sp(n+1)/Sp(n)$.

In this case $G/H$ is associated with the quaternion symmetric
$G/K=Sp(n+1)/Sp(n)Sp(1)$, and $\mathfrak{m}_{0}$ is the Lie subalgebra
$sp(1)$. By Theorem 1.2, the set of Randers equigeodesic vectors for $G/H$
which is contained in $\mathfrak{m}$ is
$\mathfrak{c}(\mathfrak{m}_{0})\backslash\\{0\\}=\emptyset$.

Case 3: $G/H=Sp(n+1)U(1)/Sp(n)U(1)$.

In this case, the decomposition
$\mathfrak{m}=\mathfrak{m}_{0}+\mathfrak{m}_{1}+\mathfrak{m}_{2}$ can be
explicitly presented as following. We choose
$\langle(A,a),(B,b)\rangle_{\mathrm{bi}}=-\mathrm{tr}AB+ab$, for
$(A,a),(B,b)\in sp(n+1)\oplus\mathbb{R}$, in which
$sp(n+1)=\\{X\in\mathbb{H}^{(n+1)\times(n+1)}|X+\overline{X}^{t}=0\\}$. The
subalgebra $\mathfrak{h}$ consists $(\mathrm{diag}(C,a\mathbf{i}),a)$ for all
$C\in sp(n)$ and $a\in\mathbb{R}$. Then $\mathfrak{m}_{0}$ consists of
$(\mathrm{diag}(0_{n\times n},a\mathbf{i}),-a)$ for all $a\in\mathbb{R}$,
$\mathfrak{m}_{1}$ consists of $(\mathrm{diag}(0_{n\times
n},b\mathbf{j}+c\mathbf{k}),0)$ for all $b,c\in\mathbb{R}$, and
$\mathfrak{m}_{2}$ consists of the pairs $(\left(\begin{array}[]{cc}0_{n\times
n}&\mathrm{v}\\\ -\overline{\mathrm{v}}^{t}&0\\\ \end{array}\right),0)$ for
all column vectors $\mathrm{v}\in\mathbb{H}^{n}$. Then direct calculations
show the following:

$\displaystyle[\mathfrak{m}_{0},\mathfrak{m}_{0}]=0,\quad[\mathfrak{m}_{0},\mathfrak{m}_{1}]\subset\mathfrak{m}_{1},\quad[\mathfrak{m}_{0},\mathfrak{m}_{2}]\subset\mathfrak{m}_{2}$
(3.12) $\displaystyle[u,v]=0\mbox{ for }u\in\mathfrak{m}_{0}\mbox{ and
}v\in\mathfrak{m}_{1}+\mathfrak{m}_{2}\mbox{ if and only if }u=0\mbox{ or
}v=0.$ (3.13)

Firstly, we prove each $X\in\mathfrak{m}_{0}\backslash\\{0\\}$ is a Randers
equigeodesic for $G/H$. Every metric operator must have the form
$\Lambda=c_{0}\mathrm{Id}|_{\mathfrak{m}_{0}}\oplus
c_{1}\mathrm{Id}|_{\mathfrak{m}_{1}}\oplus
c_{2}\mathrm{Id}|_{\mathfrak{m}_{2}}$, so
$[\Lambda(X),X]_{\mathfrak{m}}=[c_{0}X,X]=0$, and we see $X$ is a Riemannian
equigeodesic vector. It is obvious that
$[X,\mathfrak{m}_{0}]=0\subset\mathfrak{h}$. So $X$ is a Randers equigeodesic
by Theorem 1.1.

Nextly, we prove that each Randers equigeodesic $X$ for $G/H$ must belong to
$\mathfrak{m}_{0}$. Denote $X=X_{0}+X_{1}+X_{2}$ with each
$X_{i}\in\mathfrak{m}_{i}$. By Theorem 1.1,
$[X,\mathfrak{m}_{0}]=[X_{1}+X_{2},\mathfrak{m}_{0}]\subset\mathfrak{h}$.
However, by (3.12),
$[X_{1}+X_{2},\mathfrak{m}_{0}]\subset\mathfrak{m}_{1}+\mathfrak{m}_{2}$. So
$[X_{1}+X_{2},\mathfrak{m}_{0}]=0$, and it implies $X_{1}=X_{2}=0$ by (3.13).

This ends the case-by-case proof for Theorem 1.3.

Acknowledgement. This paper is supported by Beijing Natural Science Foundation
(No. 1222003), National Natural Science Foundation of China (No. 12001007, No.
12131012, No. 11821101), Natural Science Foundation of Anhui province (No.
1908085QA03).

## References

  * [1] D. V. Alekseevsky, A. Arvanitoyeorgos, Riemannian flag manifolds with homogeneous geodesics, Trans. Amer. Math. Soc. 359 (2007), 3769-3789.
  * [2] D.V. Alekseevsky and Y.G. Nikonorov, Compact Riemannian manifolds with homogeneous geodesics, SIGMA Symmetry Integr. Geom. Methods Appl. 5 (2009) 093, 16 pages.
  * [3] M. Berger, Les variétés riemanniennes homogènes normales simplement connexes à courbure strictement positive, Ann. Scuola Norm. Sup. Pisa (3) 15 (1961), 179-246.
  * [4] A. Borel, Some remarks about Lie groups transitive on spheres and tori, Bull. Amer. Math. Soc. 55 (1940), 580-587.
  * [5] D. Bao, Z. Shen and S.S. Chern, An Introduction to Riemann-Finsler Geometry, Springer-Verlag, New York, 2000.
  * [6] V.N. Berestovskii and Y.G. Nikonorov, On $\delta$-homogeneous Riemannian manioflds, Differential Geom. Appl. 26 (2008), 514-535.
  * [7] L. Cohen, L. Grama, C.J.C. Negreiros, Equigeodesics on flag manifolds, Houst. J. Math. 42 (2010), 356-374.
  * [8] S. Deng, Homogeneous Finsler spaces, Springer, New York, 2012.
  * [9] E.B. Dynkin, Semisimple subalgebras of semisimple Lie algebras, Mat. Sbornik N. S. 30 (72) (1952), 349-462, A.M.S. Translations, Series 2 6 111-244.
  * [10] Z. Dušek, O. Kowalski and S.Ž. Nikčević, New examples of g.o. spaces in dimension 7, Diff. Geom. Appl. 21 (2004), 65-78.
  * [11] S. Deng and M. Xu, Recent progress on homogeneous Finsler spaces with positive curvature, European J. Math. 3 (2017), 974-999.
  * [12] C.S. Gordon, Homogeneous Riemannian manifolds whose geodesics are orbits, in: Topics in Geometry, in Memory of Joseph D’Atri, (1996), 155-174.
  * [13] L. Grama, C.J.C. Negreiros, Equigeodesics on generalized flag manifolds with two isotropy summands, Results Math. 60 (2011), 405-421.
  * [14] C. Gordon and Y.G. Nikonorov, Geodesic Orbit Riemannian Structures on $\mathbb{R}^{n}$, J. Geom. Phys., 134 (2018), 235-243,
  * [15] S. Helgason, Differential Geometry, Lie Groups, and Symmetric Spaces, Academic Press, Inc., San Diego, 1962.
  * [16] O. Kowalski and L. Vanhecke, Riemannian manifold with homogeneous geodesics, Boll. Unione Mat. Ital., B 7 (5) (1991), 189-246.
  * [17] D. Latifi, Homogeneous geodesics in homogeneous Finsler spaces, J. Geom. Phys. 57 (2007), 1421-1433.
  * [18] O.V. Manturov, Homogeneous asymmetric Riemannian spaces with an irreducible group of motions, Dokl. Akad. Nauk. SSSR 141 (1961), 792-795.
  * [19] O.V. Manturov, Riemannian spaces with orthogonal and symplectic groups of motions and an irreducible group of rotations, Dokl. Akad. Nauk. SSSR 141 (1961), 1034-1037.
  * [20] O.V. Manturov, Homogeneous Riemannian manifolds with irreduble isotropy group, Trudy Sem. Vector. Tenzor. Anal. 13 (1966), 68-145.
  * [21] D. Montgomery and H. Samelson, Transformation groups on spheres, Ann. Math. 44 (1943), 454-470.
  * [22] Y.G. Nikonorov, Geodesic orbit Riemannian metrics on spheres, Vladikavkaz. Mat. Zh. 15 (3) (2013), 67-76.
  * [23] M. Statha, Equigeodesics on generalized flag manifolds with $G_{2}$-type $\mathfrak{t}$-roots, Osaka J. Math. 57 (2020), 871-888.
  * [24] J.A. Wolf, The geometry and structure of isotropy irreducible homogeneous spaces, Acta Math. 120 (1968), 59-148; correction, Acta Math. 152 (1984), 141-142.
  * [25] M. Wang and W. Ziller, On normal homogeneous Einstein manifolds, Ann. Sci. École Norm. Sup. (4) 18 (4) (1985), 563-633.
  * [26] Y. Wang and G. Zhao, Equigeodesic on generalized flag manifolds with $b_{2}(G/K)=1$, Results Math. 64 (2013), 77-90.
  * [27] M. Xu, Geodesic orbit spheres and constant curvature in Finsler geometry, Diff. Geom. Appl. 61 (2018).
  * [28] M. Xu, Geodesic orbit Finsler spaces with $K\geq 0$ and the (FP) condition, Advances in Geometry 21 (4) (2021), 551-564.
  * [29] M. Xu and S. Deng, Normal homogeneous Finsler spaces, Transform. Groups 22 (4) (2017), 1143-1183.
  * [30] Z. Yan, Some Finsler spaces with homogeneous geodesics, Math. Nachr. 290 (2-3) (2017), 474-481.
  * [31] Z. Yan and S. Deng, Finsler spaces whose geodesics are orbits, Diff. Geom. Appl. 36 (2014), 1-23.
  * [32] W. Ziller, Weakly symmetric spaces, in: Gindikin, S., Simon, B. (eds.) Topics in Geometry: In Memory of Joseph D’Atri, 355-368, Birkhäuser, Boston, 1996.
  * [33] L. Zhang and M. Xu, Standard homogeneous $(\alpha_{1},\alpha_{2})$-metrics and geodesic orbit property, Math. Nachr. (2022), doi:10.1002/mana.201900536.


Copyright © 2023 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).

8th International Workshop on Satisfiability Checking and Symbolic
Computation, July 28, 2023, Tromsø, Norway, Collocated with ISSAC 2023

[orcid=0000-0003-3769-5478<EMAIL_ADDRESS>url=https://sites.google.com/view/tereso, ]

[orcid=0000-0001-5729-3420<EMAIL_ADDRESS>url=https://matthewengland.coventry.domains, ]

# Data Augmentation for Mathematical Objects

Tereso del Río  Coventry University, UK  Matthew England

(2023)

###### Abstract

This paper discusses and evaluates ideas of data balancing and data
augmentation in the context of mathematical objects: an important topic for
both the symbolic computation and satisfiability checking communities, when
they are making use of machine learning techniques to optimise their tools. We
consider a dataset of non-linear polynomial problems and the problem of
selecting a variable ordering for cylindrical algebraic decomposition to
tackle these with. By swapping the variable names in already labelled
problems, we generate new problem instances that do not require any further
labelling when viewing the selection as a classification problem. We find this
augmentation increases the accuracy of ML models by 63% on average. We study
what part of this improvement is due to the balancing of the dataset and what
is achieved thanks to further increasing the size of the dataset, concluding
that both have a very significant effect. We finish the paper by reflecting on
how this idea could be applied in other uses of machine learning in
mathematics.

###### keywords:

Machine Learning Data Balancing Data Augmentation Cylindrical Algebraic
Decomposition

##  1 Introduction

###  1.1 Machine learning and cylindrical algebraic decomposition

Cylindrical Algebraic Decomposition (CAD) is an algorithm which, given a set
of polynomials, decomposes the space in which they are defined into regions in
which they are sign-invariant [Collins1975x]. CAD has many potential
applications, however, its theoretical and practical complexity is doubly
exponential [Brown2007], reducing the scope of its use in practice. In recent
years, CAD has been a central component of the collaboration between the
Symbolic Computation and Satisfiability Checking communities which meet in
this SC2 workshop. For example, there have been adaptions of CAD for use as an
SMT theory solver [Kremer2020], a repackaging of CAD theory into new
algorithms better suited for satisfiability (namely cylindrical algebraic
coverings [Abraham2021] and the use of CAD in the model constructing calculus
[Jovanovic2012]), and the NuCAD algorithm which uses some of these ideas to
tackle more general quantifier elimination problems [Brown2015].

CAD requires a declared variable ordering. In the satisfiability context, the
variable ordering is unspecified (any may be chosen to gain a correct result),
and in the quantifier elimination context, there is freedom within quantifier
blocks (as swapping the order of quantified variables changes the meaning only
if the quantifiers are different. These choices of variable ordering may not
affect the correctness of the end result but they can have a huge impact on
the resources required by these algorithms. In fact, Brown and Davenport found
in [Brown2007] that there are a family of problems for which in the worst
ordering the complexity grows doubly exponentially
($2,4,16,256,4294967296,\dots$) while another ordering has a constant
complexity.

Since the community realised the importance of variable ordering, various
human-made heuristics have been developed for the choice, e.g. [Brown2004],
[Dolzmann2004], [Bradford2013], [Wilson2015], [boulier_new_2022]. There have
also been some experiments with dynamical variable orderings in the
satisfiability context [NKA19]. None of these heuristics is perfect; all have
room for improvement in their choices. This led to a new strain of research
which applied Machine Learning (ML) models to make the choice: first in
selecting which human-made heuristic to follow [Huang2014], and later
selecting the ordering directly [Florescu2019a], [Florescu2019b], [FE20b],
[Chen2020]. While these models have demonstrated good performance, there are
barriers to their use such as the lack of meaningful training data, and the
unbalanced nature of such data that does exist.

This paper proposes to balance and augment the existing datasets by exploiting
the arbitrary nature of the variable representations within (the variable
names). We note that this idea has been independently proposed recently in the
preprint [hester_revisiting_2023]. The present paper makes similar findings on
the benefits of augmentation as [hester_revisiting_2023] and further explores
how those benefits split between solving the problem of unbalanced data and
increasing the data size.

###  1.2 Data augmentation

Data augmentation consists of generating new data instances from existing
ones. It is a widely-used technique in ML more generally, where the ability to
increase the dataset can help tackle over-fitting, and increase the accuracy
of the resulting model. Moreover, it can be used to mitigate the biases in the
dataset and to reduce the cost of labelling [Shorten2019].

Data augmentation is commonly used to generate new images in Computer Vision
ML applications. Let us take these ideas used in computer vision as an analogy
for generating new mathematical objects. For example, it is clear to any human
that a picture of an arrow pointing to the right that is rotated 90 degrees
clockwise results gives a picture of an arrow pointing downwards. This can be
very useful, imagine that your dataset contains 268 images: 4 images of arrows
pointing downwards, 35 pointing left, 56 pointing upwards, and 173 pointing to
the right. This dataset is very unbalanced, and any model trained on it would
likely have a bias towards predicting that the arrow points to the right and
against predicting that the arrow points downwards. However, by simply using
image rotations the dataset can be balanced to contain 67 images for each of
the classes. Furthermore, since you can obtain three extra images from each of
the images in the original dataset, we could actually obtain an augmented
dataset of 1072 images with 268 of each class.

Returning to our mathematical context, our objects are sets of polynomials
(possibly used to form polynomial constraints). For example,
$\\{x_{1}^{2}-x_{2},x_{3}^{3}-1\\}$. We can determine, by computing and
comparing CADs, that the optimal variable ordering to compute a CAD for this
set is $x_{2}\succ x_{1}\succ x_{3}$. Now observe that simply by swapping the
names of the variables $x_{1}$ and $x_{2}$ we may obtain the new set of
polynomials $\\{x_{2}^{2}-x_{1},x_{3}^{3}-1\\}$, in which we know, without any
further CAD computation, that the optimal variable ordering is $x_{1}\succ
x_{2}\succ x_{3}$.

###  1.3 Plan of the paper

In this paper, we will use data augmentation to balance our initially
unbalanced polynomial dataset, obtaining an improvement in the accuracy of the
models. Then, we will see how much more accuracy will be improved by
generating the maximum number of instances possible with the data augmentation
tools we have. Section 2 outlines our methodology in creating a labelled
dataset to use for ML to select a CAD variable ordering and Section 3 how we
have balanced and augmented that dataset. Then in Section 4, we compare the
performance of ML models trained and tested on these various datasets. We
finish in Section LABEL:sec:final with conclusions, a comparison with some
similar work in the preprint [hester_revisiting_2023], and ideas for future
work.

The dataset and code used to generate the datasets and results described in
this paper can be found on GitHub here:

https://github.coventry.ac.uk/delriot/AugmentingMathematicalDataset

##  2 Creating a Dataset

There are three steps towards creating a dataset suitable for ML in our
context: finding a collection of sets of meaningful polynomials, choosing a
methodology to represent each of these sets to an ML model, and then a system
for labelling them (identifying the best CAD ordering). We describe each of
these steps in the following subsections.

###  2.1 Source of polynomial problems

The collection of sets of polynomials we use will be those problems in the
QF_NRA collection of the SMT-LIB library [Barrett2016] which involve three
variables. These examples are all satisfiability problems and thus do not
represent the full application range of CAD which can also address quantifier
elimination. However, there are no sizeable datasets of QE problems we are
aware of. The problems in the SMT-LIB do mostly emit from real applications
making performance upon them meaningful. Common sources are problems include
the theorem prover MetiTarski [Paulson2012], attempts to prove termination of
term-rewrite systems, verification conditions from Keymaera [PQR09], and
curated sets of problems from geometry [BKRVV21], economics [MDE18] and
biology [BDEEGGHKRSW20].

###  2.2 Representing sets of polynomials

Representing sets of polynomials for ML is not an easy task. First, their size
can vary: we have already chosen to fix the number of variables but there
could then still be an arbitrary number of polynomials, and each of these
polynomials can have a great many different terms (although in practice each
has not very many).

To represent a set of polynomials we will follow the methodology of
[Florescu2019a] where polynomial sets are represented by a vector of real
(floating point) numbered features, with those features generated
algorithmically through simple operations generated in turn for each variable.
For example, one feature is the sum across the polynomials of the average of
the degree of $x_{1}$ across the monomials. For the set of polynomials
$\\{x_{2}^{2}-x_{2}x_{1},x_{3}^{3}x_{1}-x_{1}^{2}+1\\}$, this feature is
$3/2$, as the average degree of $x_{1}$ in the first polynomial is
$\tfrac{1}{2}$ and $1$ in the second.

As well as sum and average, the framework we use can apply the operations of
maximum, sum, average, and average of non-zero terms. We also have the
possibility of taking the sign at any point. Another example feature is the
sum across the polynomials of the sign of the sum of the degree of $x_{2}$
across the monomials (which simplifies to the number of polynomials that
contain the variable $x_{2}$). For the previous set of polynomials, this
feature is $1$, because the sum of the degree of $x_{1}$ is $3$ in the first
polynomial and $0$ in the second. Moreover, the degree of the variable can be
substituted by $sv_{x_{i}}$, the total degree of the monomial if the monomial
includes such a variable (it is 0 otherwise). E.g. $sv_{x_{1}}$ is 4 for the
monomial $x_{1}x_{2}x_{3}^{2}$ and 0 for the monomial $x_{2}^{3}x_{3}$ because
$x_{1}$ does not appear in the latter. See [Florescu2019a] for further
details.

Applying this process results in 384 features to describe a set of polynomials
in three variables, of which 195 are essentially distinct (not in a linear
relationship with any other feature in our dataset). We thus use these 195
features to represent a set of polynomials in 3 variables.

###  2.3 Labelling the sets of polynomials

In the case of sets of polynomials of three variables, there are six possible
variable orderings. A CAD has been computed in Maple [CM14a] for each ordering
for every problem in our dataset, and we timed how long this took, discarding
any example in which all orderings timed out (took more than 60 seconds). The
label of the set of polynomials is the number associated with the ordering, as
given in Table 1, whose CAD required the lowest computation time. Thus we form
a labelled dataset for an ML classification problem.

Ordering Name | Ordering
---|---
Ordering 0 | $x_{1}\succ x_{2}\succ x_{3}$
Ordering 1 | $x_{1}\succ x_{3}\succ x_{2}$
Ordering 2 | $x_{2}\succ x_{1}\succ x_{3}$
Ordering 3 | $x_{2}\succ x_{3}\succ x_{1}$
Ordering 4 | $x_{3}\succ x_{1}\succ x_{2}$
Ordering 5 | $x_{3}\succ x_{2}\succ x_{1}$
Table 1: The six possible variable orderings

##  3 Modifying the Dataset

The dataset described in the previous section has 1019 instances: 406 labelled
0, 93 labelled 1, 135 labelled 2, 51 labelled 3, 202 labelled 4 and 132
labelled 5. There is hence a clear imbalance in this dataset that will likely
result in a bias in models trained upon it.

We split this dataset into an original testing dataset containing 20% of the
instances (815) and an original training dataset containing the rest.

###  3.1 Balancing the dataset

We first randomly changed the label of each instance permuting the variable
names in the underlying polynomials. This is done in both of the original
datasets (training and testing), obtaining a balanced training dataset and a
balanced testing dataset of the same sizes as the original training and
testing sets.

###  3.2 Augmenting the dataset

However, nothing is stopping us from adding all of the six possible re-
orderings for each problem to the dataset: each would have a different label
which we know without any further labelling. By adding all the possibilities
we obtain a perfectly balanced dataset with six times more data than the
original one. The sizes of all these datasets are shown in Table
LABEL:tab:instances_datasets.

Dataset | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---